day45

1、leetcode70 爬楼梯

1. 需要 n 阶才能到达楼顶，每次可以爬 1 或 2 个台阶。

   • 转化为完全背包问题
     • 背包容量：n
     • 物品【物品可以反复使用】
       • 价值：1、2
       • 重量（所占背包容量）：1

2. 代码

   class Solution {
       public int climbStairs(int n) {
           //dp[j] : 爬到第j阶有dp[j]种方法
           int[] dp = new int[n+1];
           dp[0] = 1;
   
           for(int j=1; j<=n; j++) { //先遍历背包
               for(int i=1; i<=2; i++) { //再遍历物品 【该遍历顺序 ==> 求排列数】
                   if(j >= i) {
                       dp[j] += dp[j-i];
                   }
               }
           }
           
           return dp[n];
       }
   }
   

2、leetcode322 零钱兑换

1. 完全背包问题

   1. 背包容量：amount
   2. 物品：硬币【每一个硬币均可反复使用】

2. 代码 【该题可以先遍历物品再遍历背包（求组合数）； 也可以先遍历背包再遍历物品（求排列数）】【因为硬币有没有顺序均不影响硬币的最小个数】

   class Solution {
       public int coinChange(int[] coins, int amount) {
           //dp[amount]: 凑成金额为amount的最少硬币个数
           int[] dp = new int[amount+1];
           int max = Integer.MAX_VALUE;
   		
           //因为每次dp[j]都要选最小的，所以非0下标的dp[j]一定要初始为最大值，这样dp[j]在递推的时候才不会被初始值覆盖
           for(int i=0; i<dp.length; i++) dp[i] = max;
           dp[0] = 0;
   
           for(int i=0; i<coins.length; i++) {// 遍历物品
               for(int j=coins[i]; j<= amount; j++) {// 遍历背包
                   if(dp[j-coins[i]] != max) {// 如果dp[j - coins[i]]是初始值则跳
                       dp[j] = Math.min(dp[j], dp[j-coins[i]]+1);
                   }
               }
           }
   
           return dp[amount] == max ? -1 : dp[amount];
       }
   }
   

3、leetcode279 完全平方数

1. 思路同上一题

2. 代码

   class Solution {
       public int numSquares(int n) {
           //dp[j]：和为j的完全平方数的最少数量为dp[j]
           int[] dp = new int[n+1];
           int max = Integer.MAX_VALUE;
   		
           //因为每次dp[j]都要选最小的，所以非0下标的dp[j]一定要初始为最大值，这样dp[j]在递推的时候才不会被初始值覆盖
           for(int i=0; i<dp.length; i++) {
               dp[i] = max;
           }
           dp[0] = 0;
   		
           //因为求最小数，遍历顺序无影响，组合排列不会影响最小个数
           for(int j=0; j<=n; j++) {
               for(int i= 1; i*i<=j; i++) {
                   dp[j] = Math.min(dp[j], dp[j-i*i]+1);
               }
           }
   
           return dp[n];
   
       }
   }