70. 爬楼梯
爬楼梯问题其实是一个完全背包问题!
是求一个排列问题
所以遍历顺序 需将target放在外循环,将nums放在内循环。
class Solution {
public int climbStairs(int n) {
int[] dp = new int[n + 1];
dp[0] = 1;
int[] step = new int[2];
step[0] = 1;
step[1] = 2;
for(int i = 1; i <= n; i++){
for(int j = 0; j < step.length; j++){
if(step[j] <= i){
dp[i] += dp[i-step[j]];
}
}
}
return dp[n];
}
}
322. 零钱兑换
题目中说每种硬币的数量是无限的,可以看出是典型的完全背包问题。
1.确定dp数组以及下标的含义
dp[j]:凑足总额为j所需钱币的最少个数为dp[j]
2. 确定递推公式
dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
3. dp数组如何初始化
首先凑足总金额为0所需钱币的个数一定是0,那么dp[0] = 0
考虑到递推公式的特性,dp[j]必须初始化为一个最大的数
4. 确定遍历顺序
如果求组合数就是外层for循环遍历物品,内层for遍历背包。
如果求排列数就是外层for遍历背包,内层for循环遍历物品
所以本题并不强调集合是组合还是排列。
所以本题的两个for循环的关系是:外层for循环遍历物品,内层for遍历背包或者外层for遍历背包,内层for循环遍历物品都是可以的!
5. 举例推导dp数组
class Solution {
public int coinChange(int[] coins, int amount) {
int max = Integer.MAX_VALUE;
int[] dp = new int[amount + 1];
dp[0] = 0;
for(int i = 1; i <= amount; i++){
dp[i] = max;
}
for(int i = 0; i < coins.length; i++){
for(int j = coins[i]; j <= amount; j++){
if(dp[j - coins[i]] != max){
dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
}
}
}
return dp[amount] == max ? -1 : dp[amount];
}
}
279. 完全平方数
题目翻译一下:完全平方数就是物品(可以无限件使用),凑个正整数n就是背包,问凑满这个背包最少有多少物品?
其实和上一题几乎差不多
class Solution {
public int numSquares(int n) {
int[] dp = new int[n+1];
int max = Integer.MAX_VALUE;
dp[0] = 0;
for(int i = 1; i <= n; i++){
dp[i] = max;
}
for(int i = 1; i * i <= n; i++){
int squar = i * i;
for(int j = squar; j <= n; j++){
if(dp[j - squar] != max){
dp[j] = Math.min(dp[j], dp[j - squar] + 1);
}
}
}
return dp[n];
}
}