代码随想录算法训练营第三十八天-动态规划-完全背包-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];}
  };
  

  • 汇总