2023年10月23日 - 动态规划7

70. 爬楼梯

dp[i]：爬到有i个台阶的楼顶，有dp[i]种方法。

排列问题，物品顺序算数，所以需要先遍历背包，再遍历物品，这样子物品就会有先后顺序；同时需要从前往后遍历

这个题有一个额外的条件，m表示最多可以爬m个台阶

 class Solution {
 public:
     int climbStairs(int n) {
         vector<int> dp(n + 1, 0);
         dp[0] = 1;
         for (int i = 1; i <= n; i++) { // 遍历背包
             for (int j = 1; j <= m; j++) { // 遍历物品
                 if (i - j >= 0) dp[i] += dp[i - j];
             }
         }
         return dp[n];
     }
 };

322. 零钱兑换

如果求组合数就是外层for循环遍历物品，内层for遍历背包。这样子就不会重复

如果求排列数就是外层for遍历背包，内层for循环遍历物品。

内层从大到小还是从小到大取决于是否可以重复取

注意初始化的值，背包为0的时候答案就是0，所以dp[0] = 0,下标非零由于是min,所以需要初始化为INT_MAX

 class Solution {
 public:
     int coinChange(vector<int>& coins, int amount) {
         vector<int> dp(amount + 1, INT_MAX);
         dp[0] = 0;
         for (int i = 0; i < coins.size(); i++) { // 遍历物品
             for (int j = coins[i]; j <= amount; j++) { // 遍历背包
                 if (dp[j - coins[i]] != INT_MAX) { // 如果dp[j - coins[i]]是初始值则跳过
                     dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
                 }
             }
         }
         if (dp[amount] == INT_MAX) return -1;
         return dp[amount];
     }
 };

279. 完全平方数

 class Solution {
 public:
     int numSquares(int n) {
         vector<int> dp(n + 1, INT_MAX);
         dp[0] = 0;
         for (int i = 1; i * i <= n; i++) { // 遍历物品
             for (int j = i * i; j <= n; j++) { // 遍历背包
                 dp[j] = min(dp[j - i * i] + 1, dp[j]);
             }
         }
         return dp[n];
     }
 };