代码随想录第四十五天|70、322、279
- Leetcode 70. 爬楼梯
- Leetcode 322. 零钱兑换
- Leetcode 279. 完全平方数
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];}
}