您现在的位置是：首页 >其他 >代码随想录第四十五天|爬楼梯、零钱兑换、完全平方数网站首页其他

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];
    }
}