leetcode 刷题 log day 45

• 70. 爬楼梯 （进阶）
  【思路】要上的台阶数就是背包容量，每次只能上一个台阶或者两个台阶，就是物品的值。因为要考虑排列顺序，所以先遍历背包后遍历物品，分析完毕套公式～

  // 斐波那契做法
  var climbStairs = function(n) {
      let dp = [0, 1, 2];
      for (let i = 3; i <= n; i++) {
          dp[i] = dp[i - 1] + dp[i - 2];
      }
      return dp[n];
  };
  
  // 动态规划：完全背包
  var climbStairs = function(n) {
    let dp = new Array(n + 1).fill(0);
    dp[0] = 1;
    for (let i = 1; i <= n; i++) {  // 因为是求排列，要考虑顺序，所以是先遍历背包后遍历物品 
      for (let j = 1; j <= 2; j++) {
        if (i >= j) dp[i] += dp[i - j];
      }
    }
    return dp[n];
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20

• 322. 零钱兑换
  【思路】背包容量为 amount，因为要求最少硬币个数，所以公式取最小值，为 dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1)，每次上一个硬币个数上加一个硬币（求个数的话才加一，求有多少种方法就不加一：dp[j] += dp[j - nums[i]]）。因为只求个数不看顺序，所以遍历顺序随意～

  var coinChange = function(coins, amount) {
    let dp = new Array(amount + 1).fill(Infinity);
    dp[0] = 0;
    
    for (let i = 0; i < coins.length; i++) {
      for (let j = coins[i]; j <= amount; j++) {
        dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
      }
    }
    
    return dp[amount] !== Infinity ? dp[amount] : -1;
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12

• 279. 完全平方数
  【思路】可以把 n 看作背包容量，那么物品就是自然数，值就是自然数的平方。因为又是求个数，所以公式里有 +1。

  var numSquares = function(n) {
    let dp = new Array(n + 1).fill(Infinity);
    dp[0] = 0;
  
    for (let i = 1; i * i <= n; i++){
      for (let 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

参考代码随想录：https://www.programmercarl.com/