LC70. 爬楼梯
原题其实是一道简单动规的题目。但其实本题稍加改动就是一道面试好题。
-
如改为：一步一个台阶，两个台阶，三个台阶，.......，直到 m个台阶。问有多少种不同的方法可以爬到楼顶呢？
-
1阶，2阶，.... m阶就是物品，楼顶就是背包。每一阶可以重复使用，例如跳了1阶，还可以继续跳1阶。问跳到楼顶有几种方法其实就是问装满背包有几种方法。
-
这样和“组合总和Ⅳ”基本就是同样思路的了（完全背包求刚好装满的方法数）
代码中m表示最多可以爬m个台阶，代码中把m改成2就是本题70.爬楼梯可以AC的代码了
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];
}
LC322. 零钱兑换
开始把dp数组中非零下标的元素都设置成了INT32_MAX，但会导致在做dp[j - coins[i]] + 1运算时INT溢出，此时在第二个for内加多一个 if (dp[j - coins[i]] != INT_MAX) 判断也可以。
int coinChange(vector<int>& coins, int amount)
{
int size = coins.size();
////不存在amount + 1个数相加之和会超过amount，因为coin值最小为1
vector<int> dp(amount + 1, amount + 1);
dp[0] = 0;
for (int i = 0; i < size; ++i)
{
for (int j = coins[i]; j <= amount; ++j)
{
dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
}
}
return dp[amount] == (amount + 1) ? -1 : dp[amount];
}
LC279. 完全平方数
int numSquares(int n)
{
vector<int> dp(n + 1, n + 1);
dp[0] = 0;
vector<int> package;
int num = 1;
int square = 1;
while (n >= square)
{
package.emplace_back(square);
++num;
square = num * num;
}
int size = package.size();
for (int i = 0; i < size; ++i)
{
for (int j = package[i]; j <= n; ++j)
{
dp[j] = min(dp[j - package[i]] + 1, dp[j]);
}
}
return dp[n];
}