279.完全平方数

https://leetcode-cn.com/problems/perfect-squares/
image.png
定义dp[i]：
给定正整数i，完全平方数的最小数量
转移方程：
1.不装入：dp[i]
2.装入：dp[i - j * j] + 1

  • 背包每次减少的容量wt：j*j

  • 背包每次增加的价值v：1

    1. var numSquares = function(n) {
    2.   if (n === 0) {
    3.       return 0;
    4.   }
    5.   let dp = new Array(n + 1);
    6.   dp[0] = 0;
    7.   for (let i = 1; i <= n; i++) {
    8.       dp[i] = i;
    9.       for (let j = 1; j * j <= i; j++) {
    10.           dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
    11.       }
    12.   }
    13.   return dp[n];
    14. };

    322.零钱兑换

    https://leetcode-cn.com/problems/coin-change/
    image.png
    定义dp[i]：
    面值为i的硬币，凑成总额的最小硬币数量
    转移方程：
    1.不装入：dp[i]
    2.装入：dp[i - c] + 1

  • 背包每次减少容量：c

  • 背包每次增加价值：1
    /**
* @param {number[]} coins
* @param {number} amount
* @return {number}
*/
var coinChange = function (coins, amount) {
  let dp = new Array(amount + 1);
  dp[0] = 0;
  for (let i = 1; i <= amount; i++) {
      dp[i] = Infinity;
      for (let c of coins) {
          // 小心溢出
          if (i >= c && dp[i - c] !== Infinity) {
              dp[i] = Math.min(dp[i], dp[i - c] + 1);
          }
      }
  }
  if (dp[amount] === Infinity) {
      return -1;
  }
  return dp[amount];
};

    494.目标和

    image.png