70. 爬楼梯
思路
这道题目要求有序，因此是全背包的排列做法。
1.数组下标以及含义
dp[i]：爬到n台阶一共有dp[i]种方法。
2.递推关系
dp[i] += dp[i - j];
3.初始化
dp[0]=1可以实现递推关系
4.遍历顺序
先遍历背包（n），再遍历物品（每次的台阶数）
实现
点击查看代码
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 <= 2; j++) {
if(i-j >=0)dp[i] += dp[i - j];
}
}
return dp[n];
}
};
复杂度分析
- 时间复杂度：O(n×m)，本题中m为2
- 空间复杂度：O(n)
322. 零钱兑换
思路
这道题目求所需最少的硬币个数，既没有要求与顺序有关，也没有要求与顺序无关，因此两种遍历顺序都可以。
1.数组以及下标含义
dp[j]:凑成总金额j所需要的最少的硬币个数
2.递推关系
dp[j] = min(dp[j],dp[j-coins[i]]+1);
3.初始化
当总金额为0时，所需要的硬币个数为0，因此dp[0] = 0;
要求求出最小个数，初始化其他的数为最大int值。
4.遍历顺序
两种遍历都可以。
实现
class Solution {
public:
int coinChange(vector
vector
dp[0] = 0;
for(int i = 0; i < coins.size(); i++) {
for(int j = coins[i]; j <= amount; j++) {
if(dp[j - coins[i]] != INT32_MAX)dp[j] = min(dp[j], dp[j - coins[i]] + 1);
}
}
if (dp[amount] == INT32_MAX) return -1;
return dp[amount];
}
};
复杂度分析
- 时间复杂度：O(m×n)，m为target，n为硬币种类
- 空间复杂度：O(n)
279. 完全平方数
思路
与上一道题思路相同。n为背包重量，小于n的平方数时物品。
实现
点击查看代码
class Solution {
public:
int numSquares(int n) {
vector<int> dp(n+1, 10000);
dp[0] = 0;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= sqrt(i); j++) {
dp[i] = min(dp[i], dp[i - j*j] + 1);
}
cout<<dp[i]<<endl;
}
return dp[n];
}
};
复杂度分析
- 时间复杂度：O(nlogn)，logn为小于n的平方数的数量
- 空间复杂度：O(n)