LeetCode70. 爬楼梯(进阶)
题目链接:70. 爬楼梯(进阶)
独上高楼,望尽天涯路
可以把爬楼梯看成是一个排序问题加完全背包。
class Solution {
public:
int climbStairs(int n) {
vector<int> stairs = {1, 2};
vector<int> dp(n + 1, 0);
dp[0] = 1;
for (int j = 0; j < n + 1; j++) {
for (int i = 0; i < stairs.size(); i++) {
if (j - stairs[i] >= 0) dp[j] += dp[j - stairs[i]];
}
}
return dp[n];
}
};
慕然回首,灯火阑珊处
思路一样。
LeetCode322. 零钱兑换
题目链接:322. 零钱兑换
独上高楼,望尽天涯路
看起来和之前套路一样的题,写起来还是有很多细节需要注意的。
慕然回首,灯火阑珊处
这是典型的完全背包问题,用到了新的递推公式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); // 注意需要初始化为INT_MAX
dp[0] = 0;
for (int i = 0; i < coins.size(); i++) {
for (int j = coins[i]; j < amount + 1; j++) {
// 这里的含义是如果选择物品i,剩下的背包容量不能正好被其他物品填满,则不更新dp[j]
if (dp[j - coins[i]] != INT_MAX) {
dp[j] = min(dp[j], dp[j - coins[i]] + 1);
}
}
}
if(dp[amount] == INT_MAX) return -1;
return dp[amount];
}
};
LeetCode279. 完全平方数
题目链接: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 + 1; j++) {
dp[j] = min(dp[j], dp[j - i * i] + 1);
}
}
return dp[n];
}
};
慕然回首,灯火阑珊处
思路一样。
标签:LeetCode70,进阶,int,MAX,coins,LeetCode279,amount,vector,dp From: https://www.cnblogs.com/BarcelonaTong/p/17124939.html