代码随想录训练营二刷第四十七天 | 70. 爬楼梯 （进阶） 322. 零钱兑换 279.完全平方数

代码随想录训练营二刷第四十八天 | 70. 爬楼梯 （进阶） 322. 零钱兑换 279.完全平方数

一、70. 爬楼梯 （进阶）

题目链接：https://leetcode.cn/problems/climbing-stairs/
思路：物品是楼梯1和2，背包是n求排列数，背包在外物品在内，递推公式dp[i] += dp[i - j]

class Solution {
    public int climbStairs(int n) {
        int[] dp = new int[n+1];
        dp[0] = 1;
        for (int i = 0; i <= n; i++) {
            for (int j = 1; j <= 2; j++) {
                if (j <= i) {
                    dp[i] += dp[i - j];
                }
            }
        }
        return dp[n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

二、322. 零钱兑换

题目链接：https://leetcode.cn/problems/coin-change/
思路：求所需物品的最少数量，完全背包，定义dp[i]表示背包容量为i时所需物品的最少数量，递推公式dp[i] = dp[i-j] + 1。自然等于放这个物品的前一个位置加1。如dp[5] = dp[5 - 1] + 1 或者 dp [5 - 2] + 1等等，一定得是这些当中最少的那个。故dp[j] = Math.min(dp[j], dp[j-coins[i]] + 1)。最少数量无关排列或者组合。初始化为最大值，dp[0]=0，另外必须得是dp[j-coins[i]] != max时才能进行递推，如果dp[j-coins[i]] == max说明前一个数就没用，现在当前不能在没使用的基础上进行递推。

class Solution {
   public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount+1];
        int max = Integer.MAX_VALUE;
        for (int i = 1; i < dp.length; 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];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

三、279.完全平方数

题目链接：https://leetcode.cn/problems/perfect-squares/
思路：和上题基本一样，细节在于完全平方数为i*i

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n+1];
        int max = Integer.MAX_VALUE;
        for (int i = 1; i < dp.length; i++) {
            dp[i] = max;
        }
        for (int i = 1; i*i <= n; i++) {
            for (int j = i*i; j <= n; j++) {
                dp[j] = Math.min(dp[j], dp[j - i*i] + 1);
            }
        }
        return dp[n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15