70. 爬楼梯 （进阶）
一次跨1-m个台阶为物品，共有n个台阶为背包容量，排列问题，完全背包
import java.util.*;
public class Main {
public static void main (String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[] dp = new int[n+1];
dp[0] = 1;
for(int j = 1; j <= n; j++) {//背包
for(int i = 1; i <= m; i++) {//物品
if(j >= i) {
dp[j] += dp[j - i];
}
}
}
System.out.println(dp[n]);
}
}
322. 零钱兑换
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。
本题求零钱个数，组合和排序都可以
注意初始化 递推公式
凑不齐就跳过
先背包再物品 排列
class Solution {
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
int max = Integer.MAX_VALUE;//求最小个数，初始化最大值，使之不能被覆盖
for(int j = 0; j <= amount;j++) {
dp[j] = max;
}
dp[0] = 0;//当总金额为0时，不取钱，钱的个数为0， 其他金额的初始值为max
for(int j = 0; j <= amount; j++) {//背包zhengxu
for(int i = 0; i < coins.length; i++) {//物品
if(j >= coins[i] && dp[j - coins[i]] != max) {//跳过最大值，因为最大值不能被满足，永远凑不齐
dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);//取小值
}
}
}
return dp[amount] == max ? -1 : dp[amount];//若dp[amount] 为max时，凑不齐，返回-1，其他时候返回dp[amount]
}
}先物品再背包 组合
class Solution {
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
int max = Integer.MAX_VALUE;//求最小个数，初始化最大值，使之不能被覆盖
for(int j = 0; j <= amount;j++) {
dp[j] = max;
}
dp[0] = 0;//当总金额为0时，不取钱，钱的个数为0， 其他金额的初始值为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];//若dp[amount] 为max时，凑不齐，返回-1，其他时候返回dp[amount]
}
}279.完全平方数
区别在于不用判断是否能凑齐 因为有1 必然凑齐
class Solution {
public int numSquares(int n) {
//完全背包 组合排列都可 求数量
//注意初始化成最大值 以及 dp[0] = 0
int[] dp = new int[n+1];
int max = Integer.MAX_VALUE;
for(int j = 0; j <= n; j++) {
dp[j] = max;
}
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);//因为有1*1的存在，每个数都可以被凑齐 相较于上一题不需要格外判断是否能够凑齐
}
}
return dp[n];
}
}
