題目描述

這道題是0-1背包問題。可以理解為，有一個最大容量是n的背包，有n個物品，第i個物品的重量是i^x，問裝滿背包有多少種裝法。題目要求必須是互不相同的數的x次冪的和等于n，那就表示每個數只能用一次，也就是每個物品只有一個，所以這個問題是0-1背包問題。

?

class Solution {
public:int numberOfWays(int n, int x) {//從[1,n]選若干個數使得這些數的x次冪之和等于j,dp[j]表示選法數量//初始情況，沒有數可選，j>=1時，無法選擇數字湊成總和等于j，因此dp[j](j>=1)應該初始化為0vector<long long> dp(n+1,0);//使用int類型，會報整數溢出錯誤//初始情況，沒有數可選，要想湊成總和為0只有一種選法，那就是一個數也不選，不選也是一種選法//所以dp[0]應該初始化為1dp[0] = 1;for(int i = 1;i <= n;i++){//對數字遍歷，即對物品遍歷for(int j = n;j >= pow(i,x);j--){//對總和遍歷，即對容量遍歷dp[j] = dp[j] + dp[j-pow(i,x)];//使用滾動數組}}int mod = (int)1e9+7;return dp[n]%mod;}
};