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

参考代码：

未优化代码：

class Solution {
public:int coinChange(vector<int>& coins, int amount) {int n = coins.size();const int INF = 0x3f3f3f3f;//多开一行，多开一列vector<vector<int>> dp(n + 1, vector<int>(amount + 1));//初始化dp[0][0] = 0;for (int j = 1; j <= amount; j++){//根据后面填表时取min的性质，所以无效值应该设置成正无穷大dp[0][j] = INF;}//填表for (int i = 1; i <= n; i++){for (int j = 0; j <= amount; j++){dp[i][j]=dp[i - 1][j];if(j>=coins[i-1]){//注意，这里是取min，所以不存在的值应该设成正无穷大才对，不能选择-1作为无效值dp[i][j]=min(dp[i][j],dp[i][j - coins[i - 1]]+1);}}}return dp[n][amount]>=INF?-1:dp[n][amount];}
};

优化后的代码：

class Solution {
public:int coinChange(vector<int>& coins, int amount) {int n = coins.size();const int INF = 0x3f3f3f3f;//多开一行，多开一列//初始化vector<int> dp(amount + 1,INF);dp[0] = 0;//填表for (int i = 1; i <= n; i++){for (int j = coins[i-1]; j <= amount; j++){//注意，这里是取min，所以不存在的值应该设成正无穷大才对，不能选择-1作为无效值dp[j]=min(dp[j],dp[j - coins[i - 1]]+1);}}return dp[amount]>=INF?-1:dp[amount];}
};

你学会了吗？？？