力扣 -- 518. 零钱兑换 II（完全背包问题）

解题步骤：

参考代码：

未优化代码：

class Solution {
public:int change(int amount, vector<int>& coins) {int n=coins.size();//多开一行，多开一列vector<vector<int>> dp(n+1,vector<int>(amount+1));//初始化dp[0][0]=1，其它的dp[0][j]都为0，因为不存在，所以只有0种选法dp[0][0]=1;//不要把dp[0][j]剩下的值初始化成-1，曾经因初始化成-1而出错//第一列不需要初始化//填表for(int i=1;i<=n;i++){//记得从0开始for(int j=0;j<=amount;j++){dp[i][j]=dp[i-1][j];if(j>=coins[i-1]&&dp[i][j-coins[i-1]]!=0){dp[i][j]+=dp[i][j-coins[i-1]];}}}//返回值return dp[n][amount];}
};

优化后代码：

class Solution {
public:int change(int amount, vector<int>& coins) {int n=coins.size();vector<int> dp(amount+1);//初始化dp[0]=1;//填表for(int i=1;i<=n;i++){for(int j=coins[i-1];j<=amount;j++){if(dp[j-coins[i-1]]!=0){dp[j]+=dp[j-coins[i-1]];}}}//返回值return dp[amount];}
};

你学会了吗？？？