一、最长递增子序

var lengthOfLIS = function(nums) {
    let n = nums.length
    if(!n) {
        return 0
    }
    let dp = new Array(n).fill(1)
    for(let i = 1;i < n; i++) {
        for(let j = 0;j < i; j++) {
            if(nums[i] > nums[j]) {
                dp[i] = Math.max(dp[i], dp[j] + 1)
            }
        }
    }
    return Math.max(...dp)
};

二、最小编辑距离

var minDistance = function(word1, word2) {
    let n1 = word1.length;
    let n2 = word2.length;
    let dp = new Array(n1 + 1)
    for (let i = 0; i < n1 + 1; i++) {
        dp[i] = new Array(n2 + 1).fill(0)
    }
    for (let j = 1; j <= n2; j++) {
        dp[0][j] = dp[0][j - 1] + 1;
    }
    for (let i = 1; i <= n1; i++) {
        dp[i][0] = dp[i - 1][0] + 1;
    }
    for (let i = 1; i <= n1; i++) {
        for (let j = 1; j <= n2; j++) {
            if (word1[i - 1] == word2[j - 1]){
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]) + 1;
            }         
        }
    }
    return dp[n1][n2];
};

三、高楼扔鸡蛋

//递归+动态规划
var superEggDrop = function(k, n) {
    var map = {}
  var dp = function(_k, _n) {
      if(_k === 1) {
        return n;
    }
    if(_n === 0) {
        return 0;
    }
    let res = 0
    if map(_k + ',' + _n) {
        return map(_k + ',' + _n)
    }
    for(let i = 0;i <= _n;i++) {
        res = Math.min(res, Math.max(dp(_k, _n-i), dp(_k-1, i-1)) + 1)
    }
    map(_k + ',' + _n) = res
    return res
  }
  return dp(k, n)
};
//动态规划+新的转移方程
let superEggDrop = function(K, N) {
    const dp = Array(K+1).fill(0)
  let res = 0
  while(dp[K] < N) {
    res++
      for(let i = K;i > 0;i--) {
        dp[i] = dp[i-1] + dp[i] + 1
    }
  }
  return res
}

四、最长公共子序

五、最长回文子序

var longestPalindromeSubseq = function(s) {
    let len = s.length
  let dp = new Array(len)
  for(let i = 0;i < len;i++) {
      dp[i] = new Array(len).fill(0)
  }
  for(let i = len-1;i >= 0;i--) {
      dp[i][i] = 1
    for(let j = i+1;j < len;j++){
        if(s[i] === s[j])    {
          dp[i][j] = dp[i+1][j-1] + 2
      } else {
          dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1])
      }
    }
  }
  return dp[0][len-1]
};

八、打家劫舍I

var rob = function (nums) {
    let n = nums.length;
    // 记录 dp[i+1] 和 dp[i+2]
    let dp_i_1 = 0, dp_i_2 = 0;
    // 记录 dp[i]
    let dp_i = 0;
    for (let i = n - 1; i >= 0; i--) {
        dp_i = Math.max(dp_i_1, nums[i] + dp_i_2);
        dp_i_2 = dp_i_1;
        dp_i_1 = dp_i;
    }
    return dp_i;
};

九、打家劫舍II

var rob = function (nums) {
    let n = nums.length;
    if (n === 1) return nums[0];
    // 仅计算闭区间 [start,end] 的最优结果
    let robRange = function (nums, start, end) {
        let dp_i_1 = 0, dp_i_2 = 0;
        let dp_i = 0;
        for (let i = end; i >= start; i--) {
            dp_i = Math.max(dp_i_1, nums[i] + dp_i_2);
            dp_i_2 = dp_i_1;
            dp_i_1 = dp_i;
        }
        return dp_i;
    }
    return Math.max(
        robRange(nums, 0, n - 2),
        robRange(nums, 1, n - 1)
    )
};

九、打家劫舍III

var rob = function (root) {
    let res = dp(root);
    return Math.max(res[0], res[1]);
};
var dp = function (root){
    if(root == null){
        return [0,0];
    }
    let left = dp(root.left);
    let right = dp(root.right);
    // 抢，下家就不能抢了
    let rob = root.val + left[0] + right[0];
    // 不抢，下家可抢可不抢，取决于收益大小
    let not_rob = Math.max(left[0], left[1]) + + Math.max(right[0], right[1]);
    return [not_rob, rob]
}