代码随想录训练营二刷第四十七天 | 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];}
}

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

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