代码随想录第四十五天

Leetcode 70. 爬楼梯

题目链接: 爬楼梯
自己的思路:之前是用斐波那契做的，但是现在学了完全背包，可以将m=2拓展的更大一点，我们可以将楼顶n设为背包的容量，将m设为物品的容量，我们每次选物品，而且物品可以重复，问可以有多少种不同的选法，而且这种是要考虑顺序的问题的，所以和之前的组合总和其实是一个题目！！！！！

正确思路:

代码:

class Solution {public int climbStairs(int n) {//物品的数量int m=2;int[] dp= new int[n+1];dp[0] = 1;for (int j=0;j<=n;j++){  //遍历背包for (int i=1;i<=m;i++){  //遍历物品if (j>=i) dp[j]+=dp[j-i];}}return dp[n];}
}

Leetcode 322. 零钱兑换

题目链接: 零钱兑换
自己的思路:想不到！！！！

正确思路:这个题可以看做是一个完全背包问题，因为里面的钱是可以任意取重复个的！动规五部曲：1、dp数组的含义：dp[j]表示的是当总金额为j时组成总金额的钱币的最小数量！2、递推公式：我们拿当第i个钱币来算，如果我们不选这个钱币，那么就是dp[j]情况，那么如果选的话就是dp[j-coins[i]]+1，所以说取两者的最小值；3、dp数组初始化：dp[0]肯定是0，主要是其他的我们要初始化为什么，因为我们是求min值，所以我们应该将他们都初始化为Integer的最大值；4、遍历顺序：由于这道题是求最小的数量，所以先遍历背包和先遍历物品其实是一样的；5、打印dp数组：主要是用于debug！！！

代码:

class Solution {public int coinChange(int[] coins, int amount) {int[] dp = new int[amount+1];for (int i =0;i<dp.length;i++){dp[i] = Integer.MAX_VALUE;}dp[0] = 0;for (int i=0;i<coins.length;i++){for (int j=coins[i];j<=amount;j++) {//当dp[m]有效的时候，才可以向后更新，不然没有意义if (dp[j-coins[i]]!=Integer.MAX_VALUE){dp[j] = Math.min(dp[j],dp[j-coins[i]]+1);}}}return (dp[amount]==Integer.MAX_VALUE)?-1:dp[amount];}
}

Leetcode 279. 完全平方数

题目链接: 完全平方数
自己的思路:和上一个题基本一样，怪自己懒得思考！！！！

正确思路:只是改变了一下循环中的参数的定义，其他基本都是不变的，这个题一定可以由完全平方数组成，所以我们初始化的时候非零的索引初始化为n，因为dp[n]最大是n！！！
代码:

class Solution {public int numSquares(int n) {int[] dp = new int[n+1];for (int i =0;i<dp.length;i++){dp[i]=n;}dp[0]=0;for (int i =1;i*i<=n;i++){for (int j=i*i;j<=n;j++){if (dp[j-i*i]!=n){dp[j]=Math.min(dp[j],dp[j-i*i]+1);}}}return dp[n];}
}