代码随想录算法训练营第45天 | 70.爬楼梯(进阶), 322.零钱兑换, 279.完全平方数

70.爬楼梯(进阶)

代码随想录链接

题目

LeetCode-70.爬楼梯

爬n阶楼梯, 每次可以上一层或两层, 求有多少种不同的方式可以爬到顶.

题目分析

之前使用的是递推公式来解决这个问题, 这次使用背包问题的方式来解决这个问题.

动态规划五部曲:

• 确定dp数组及下标的含义

  \(dp[j]\)代表爬到第j层楼梯, 有\(dp[j]\)种方法.

• 确定递推公式

  求方法的数量, 公式为:

  \[dp[j] += dp[j - i]\]

• dp数组的初始化

  递加的公式公式中, \(dp[0]\)应当被被初始化为1, 这样后序的递加才能累计.

• 确定遍历顺序

  本题实际上求的是不限量的1和2的有序组合, 所以应该是先遍历背包, 再遍历物品

  for (int j = 1; j < n + 1; j++)
      for (int i = 1; i < 3; i++)
          if (j - i >= 0)
              dp[j] += dp[j - i];

• 举例推导

题解

class Solution {
public:
    int climbStairs(int n) {
        vector<int> dp(n + 1, 0);
        dp[0] = 1;
        for (int j = 1; j < n + 1; j++)
            for (int i = 1; i < 3; i++)
                if (j - i >= 0)
                    dp[j] += dp[j - i];
        return dp[n];
    }
};

322.零钱兑换

代码随想录链接

题目

LeetCode-322.零钱兑换

给定不同面额的硬币, 每种硬币数量无限, 求需要凑成给定金额最少要多少个硬币.

题目分析

本题目是求组合的完全背包问题.

动态规划五部曲:

• 确定dp数组及下标的含义

  \(dp[j]\)代表凑够j金额至少需要\(dp[j]\)个硬币

• 确定递推公式

  由于本题目求得是至少需要多少硬币, 所以递推公式应该为:

  \[dp[j] = min(dp[j], dp[j - coins[i]] + 1\]

  为什么+1呢, 因为凑够\(j - coins[i]\)需要\(dp[j - coins[i]]\)个硬币, 再多一个\(coins[i]\)硬币才能凑够\(j\), 所以要+1.

• dp数组的初始化

  因为要求最小值, 所以所有位置上的值都应该是\(INT_MAX\), 同时, 凑够0元一定是需要0个硬币, 所以 \(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] = min(dp[j], dp[j - coins[i]] + 1);

• 举例推导

题解

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] = min(dp[j], dp[j - coins[i]] + 1);
        return dp[amount] == INT_MAX ? -1 : dp[amount];
    }
};

279.完全平方数

代码随想录链接

题目

LeetCode-279.完全平方数

给定正整数n, 返回至少使用多少个完全平方数的和才能凑够这个正整数.

题目分析

实际上和上一道题目是一样的.

动态规划五部曲:

• 确定dp数组及下标含义

  \(dp[j]\)代表凑够正整数\(j\)至少需要\(dp[j]\)个完全平方数.

• 确定递推公式

  由于是求至少需要多少个, 所以递推公式应当为:

  \[dp[j] = min(dp[j], dp[j - i * i] + 1)\]

• dp数组的初始化

  凑够0需要的完全平方数的个数一定为0, 所以dp[0] = 0. 又因为本题目要求最小数, 所以其他值应当初始化为INT_MAX.

• 确定遍历顺序

  本题目也是两种顺序都可以, 这里给出先遍历物品后遍历背包的写法.

  for (int i = 1; i * i <= n; i++)
      for (int j = i * i; j <= n; j++)
          if (dp[j - i * i] != INT_MAX)
              dp[j] = min(dp[j], dp[j - i * i] + 1);

• 举例推导

题解

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++)
                if (dp[j - i * i] != INT_MAX)
                    dp[j] = min(dp[j], dp[j - i * i] + 1);
        return dp[n];
    }
};