day38|70. 爬楼梯(进阶)、322. 零钱兑换、279.完全平方数
70. 爬楼梯(进阶)
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例 1：
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。 1. 1 阶 + 1 阶 2. 2 阶
示例 2：
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。 1. 1 阶 + 1 阶 + 1 阶 2. 1 阶 + 2 阶 3. 2 阶 + 1 阶
问题分析：
1、确定dp数组以及下标的含义
dp[j]：爬到 j 阶有多少种方法
2、确定递推公式
完全背包，重复利用物品，且为排列数
楼顶为背包，每次爬的阶数为物品
所以递推公式为：
dp[j]=dp[j]+dp[j-i]
3、dp数组初始化
初始化dp[0]=1
4、确定遍历顺序
本题要求是排列数，{2,1}和{1,2}是两种方法，所以先遍历背包。列排序中，阶数1和阶数2都在同层出现，所以会出现{1,2}和{2,1}，为排列数
5、打印dp数组
class Solution {public int climbStairs(int n) {int[] dp=new int[n+1];dp[0]=1;for (int j=0;j<=n;j++){for (int i=1;i<=2;i++){if (j>=i) {dp[j] = dp[j] + dp[j - i];}}}return dp[n];}
}322. 零钱兑换
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1：
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
示例 2：
输入：coins = [2], amount = 3
输出：-1
示例 3：
输入：coins = [1], amount = 0
输出：0
问题分析：
1、确定dp数组以及下标的含义
dp[j]：装满 j 的最少物品是dp[j]
2、确定递推公式
金额为背包，硬币为物品
选出最少的物品数，用min方法，比较上一个物品的dp[j]和需要凑齐本次的物品数+1
所以递推公式为：
dp[j]=Math.min(dp[j],dp[j-coins[i]]+1)
3、dp数组初始化
初始化dp[0]=0，非0初始化为Integer.MAX_VALUE，因为递推公式为选出最小值，防止被覆盖应该先初始化一个最大值。
4、确定遍历顺序
本题为组合数，先遍历物品，再遍历背包
5、打印dp数组
class Solution {public int coinChange(int[] coins, int amount) {int[] dp=new int[amount+1];for (int j=0;j<=amount;j++){dp[j]=Integer.MAX_VALUE;}dp[0]=0;for (int i=0;i<coins.length;i++){for (int j=coins[i];j<=amount;j++){if (dp[j-coins[i]]!=Integer.MAX_VALUE) {//避免出现面额凑不齐总金额的情况// 需要凑齐的前一步也无法凑齐//导致这一步也无法凑齐// 例如[2] 3dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);}}}/* for (int i=0;i<coins.length;i++){for (int j=0;j<=amount;j++){System.out.print(dp[j]+" ");}System.out.println("\n");}*/if (dp[amount]==Integer.MAX_VALUE) return -1;return dp[amount];}
}279.完全平方数
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
示例 1：
输入：n = 12
输出：3
解释：12 = 4 + 4 + 4
示例 2：
输入：n = 13
输出：2
解释：13 = 4 + 9
问题分析：
1、确定dp数组以及下标的含义
dp[j]：组成和为n的最少的平方和数有dp[j]个
2、确定递推公式
和为背包，数字为物品
每个物品都是平方和数，即为i*i
选出最少的物品数，用min方法，比较上一个物品的dp[j]和需要凑齐本次的物品数+1
所以递推公式为：
dp[j]=Math.min(dp[j],dp[j-i*i]+1)
3、dp数组初始化
初始化dp[0]=0，非0初始化为Integer.MAX_VALUE，因为递推公式为选出最小值，防止被覆盖应该先初始化一个最大值。
4、确定遍历顺序
本题为组合数，先遍历物品，再遍历背包
5、打印dp数组
class Solution {public int numSquares(int n) {int[] dp=new int[n+1];for (int j=0;j<=n;j++){dp[j]=Integer.MAX_VALUE;}dp[0]=0;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);}}/*for (int i=1;i*i<=n;i++){for (int j=1;j<=n;j++){System.out.print(dp[j]+" ");}System.out.println("\n");}*/return dp[n];}
}