爬楼梯 一次 1 步或者 2 步 到达 100阶 楼梯可以有多少种走法

f(99) + f(98) +。。。。+ f(1)

const climbStairs = function(n) {
  if(n === 1) {
    return 1;
  }
  if(n === 2) {
    return 2;
  }
  return climbStairs(n - 1) + climbStairs(n - 2);
};

会发现 f(99) = f(98) +f(97) f(98) 被算了两次 没必要 空间换时间一下

const hash = {};
const climbStairs = function(n) {
  if(n === 1) {
    return 1;
  }
  if(n === 2) {
    return 2;
  }
  if(hash[n]) {
    return hash[n];
  } else {
    const res = climbStairs(n - 1) + climbStairs(n - 2);
    hash[n] = res;
    return res;
  }
};

至底向上的动态规划

/**
* @param {number} n
* @return {number}
*/
const climbStairs = function(n) {
  let res = 0;
  const hash = {1: 1, 2: 2};
  for(let i = 3; i < n+1; i++) {
    hash[i] = hash[i-1] + hash[i-2]
  }
  return hash[n]
};

硬币

const coinChange = function(coins, amount) {
  const hash = [0];

  for(let i = 1; i < amount + 1; i++) {
    hash[i] = Infinity;
    for(let coinLength = 0; coinLength < coins.length; coinLength ++) {
      const res = i - coins[coinLength];
      if(res >= 0) {
        hash[i] = Math.min(hash[i], hash[res] + 1);
      }
    }
  }

  console.log(hash);
  return hash[amount] !== Infinity ? hash[amount] : -1;
};

背包

假设 c 被塞满 一共是 n 个物品 第 n 个物品只有可能 0 1 也就是放进去或者没放进去

假设 f(n, c) 代表最大值

那么 第 n 个包包没装进去 就是 f(n-1, c)

第 n 个被装进去就是 f(n - 1, c - w[n]) + v[n]

那么 f(n,c) = Math.max(f(n-1), f(c- w[n]) + v[n])

// 入参是物品的个数和背包的容量上限，以及物品的重量和价值数组
function knapsack(n, c, w, value) {
  // dp是动态规划的状态保存数组
  const dp = (new Array(c+1)).fill(0)
  let res = -Infinity;
  for(let i = 1; i <= n; i ++) {
    for(let j = c; j >= w[i]; j --) {
      dp[j] = Math.max(dp[j], dp[j - w[i]] + value[i])
      if(dp[j] > res) {
        res = dp[j]
      }
    }
  }
  return res
}

最长子序列

const arr = [10,9,2,5,3,7,101,18];
/**
 * @param {number[]} nums
 * @return {number}
 */
// 入参是一个数字序列 最长上升子序列
const lengthOfLIS = function(nums) {
  const len = nums.length;
  if(!len) return 0;
  const dp = (new Array(len)).fill(1);
  let res = 1;
  for(let i = 1; i < len; i++) {
    for(let j = 0; j < i; j++) {
      if(nums[j] < nums[i]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
        if(dp[i] > res) {
          res = dp[i];
        }
      }
    }
  }
  return res;
}