代码随想录算法训练营第三十八天-动态规划-完全背包-322. 零钱兑换
-
太难了
-
但听了前面再听这道题感觉递推公式也不是不难理解
-
动规五部曲
dp[j]代表装满容量为j（也就是目标值）的背包最少物品数量- 递推公式：
dp[j] = std::min(dp[j], dp[j - coins[i]] + 1)当使用coins[i]这张纸币时，要向前找到容量为j - coins[i]时所使用的最小物品数量，而本次用到了coins[i]这张纸币，所以总体上使用的纸币数量就又增加了1 - 初始化：
dp[0] = 0- 非0下标初始化要有不同，以往都是求max值，所以初始化为0，但本题要取min，都设为0所有结果也就都是0了，所以要将它们初始化成int的最大值
- 遍历顺序：先外循环背包容量，后内循环纸币面值；与先外循环纸币面值，后内循环背包容量都是计算数量的，无论什么顺序关系都是没有影响的
- 打印
class Solution { public: int coinChange(std::vector<int>& coins, int amount) { std::vector<int> dp(amount + 1, INT_MAX); dp.at(0) = 0; for (int i = 0; i < coins.size(); ++i) { for (int j = coins.at(i); j <= amount; ++j) { if (dp[j - coins[i]] != INT_MAX) { dp[j] = std::min(dp[j], dp[j - coins.at(i)] + 1); } } } if (dp[amount] == INT_MAX) { return -1; } return dp[amount]; } };- 汇总