Day45 | 70. 爬楼梯 (进阶), 322. 零钱兑换, 279.完全平方数
爬楼梯(进阶)
LeetCode题目:https://leetcode.cn/problems/climbing-stairs/
爬楼梯问题现在可以抽象成一个完全背包的排列问题。因为每次指定上一个台阶或者两个台阶,所以可以看成有两个分别重量和价值均为1,2的物品可以反复取用。台阶即为背包的容量。
因此,由以上推理,问题可以化为:当可以取到x的台阶容量时,有多少种方法组成。即此时dp的容量上限为x,dp[i]意为容量为x时最多有多少种组合方法。所以递推公式为dp[j] += dp[j - nums[i]];
最终两次循环第一轮循环背包容量,第二轮循环物品价值,代码如下:
class Solution {
public:int climbStairs(int n) {if(n==1) return 1;vector<int> dp(n+1,0);dp[1] = 1;dp[2] = 2;for (int i = 3;i <= n;i++) {for(int j = 1; j <= 2; j++) {dp[i] += dp[i - j];}}return dp[n];}
};
零钱兑换
LeetCode题目:https://leetcode.cn/problems/coin-change/
该问题与零钱兑换ii不同的是只求所需要的硬币数量,而不在乎硬币的种类组合等。因此完全背包的循环顺序先背包还是先物品容量均可。如果要组合则只能先物品容量循环。
因此,还是求最小装满数量,所以dp数组代表容量为i的时候装满所需要的最小数量。递推公式可得为dp[j] = min(dp[j-coins[i]] + 1,dp[j])。由于涉及到最小值计算,则dp里面数值应该初始化为INT_MAX。并在每次循环是判定,如果dp[j-coins[i]]==INT_MAX,则意味着之前的dp[j-coins[i]]就没有办法装满,因此后续也无法装满。当循环结束,如果dp[amount] == INT_MAX则说明无法装满,所以置为-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) continue;dp[j] = min(dp[j - coins[i]] + 1, dp[j]); }}if(dp[amount] == INT_MAX) dp[amount] = -1;return dp[amount];}
};
完全平方数
LeetCode题目:https://leetcode.cn/problems/perfect-squares/
该问题与零钱兑换类似,只不过物品价值信息没有提前给出,而是需要循环时候自己判定完全平方数的存在。同时因为是求装满的最小数量,不需要纠结循环顺序,因此为了方便,可以将物品价值作为外循环,进行平方数判定。同时平方数的上限可以由n的边界得到。
因此,还是求最小装满数量,所以dp数组代表容量为i的时候装满所需要的最小数量。递推公式可得为dp[j] = min(dp[j-i] + 1,dp[j])。由于涉及到最小值计算,则dp里面数值应该初始化为INT_MAX。并在每次循环是判定,如果dp[j-i]==INT_MAX,则意味着之前的dp[j-i]就没有办法装满,因此后续也无法装满。但因为1也是完全平方数,所以基本不会有影响。
最终两次循环,代码如下:
class Solution {
public:int numSquares(int n) {vector<int> dp(n + 1, INT_MAX);dp[0] = 0;for (int i = 1; i < 1e4 + 1; i++) {int a = (int)sqrt(i);if (a * a == i) {for (int j = i; j <= n; j++) {if(dp[j - i] == INT_MAX) continue;dp[j] = min(dp[j - i] + 1, dp[j]);}}}return dp[n];}
};