动态规划的实现和特性

递归和分治

递归代码模板

function recur (level, param) {
	// terminator
  if (level > MAX_LEVEL) {
    // process result
    return;
  }
  
  // process current logic
  process(level, param);
  
  // drill down
  recur(level + 1, newParam);
  
  // restore current status
}

分治代码模板

function divide_conquer (problem, param1, param2, ...) {
	// recursion terminator
  if (!problem) {
    // process result
    return;
  }
  
  // prepare data
  data = prepare_date(problem);
  subproblems = split_problem(problem, data);
  
  // conquer subproblems
  subresult1 = divide_conquer(subproblems[0], p1, ...);
  subresult2 = divide_conquer(subproblems[1], p2, ...);
  subresult3 = divide_conquer(subproblems[2], p3, ...);
  
  // process and generate the final result
  result = process_result(subresult1, subresult2, subresult3, ...);
  
  // revert current level status
}

人肉递归低效、很累；

找到最近最简方法，将其拆解为可重复解决的问题；

数学归纳法思维（抵制人肉递归诱惑）

本质：寻找重复性 => 计算机指令集只会 if else、for、recur

动态规划

动态规划 Dynamic Programming。

Divide & Conquer + Optimal substructure，分治 + 最优子结构。

动态规划定义 https://en.wikipedia.org/wiki/Dynamic_programming

"Simplifying a Complicated problem by breaking it down into simpler sub-problems" (in a recursive manner).

关键点

动态规划 和 递归 或者 分治 没有根本的区别（关键看有无最优子结构）。

共性：找到重复子问题。
差异性：最优子结构、中途可以淘汰次优解。

斐波那契数列

// 斐波那契数列是指数级的 2^n，不是 n^2

// 无优化
function fib (n) {
  if (n <= 2) return n;
  
  return fib(n - 1) + fib(n - 2);
};

// 记忆化搜索
function fib (n, memo = {}) {
  if (n <= 2) return n;
  
  if (!memo[n]) {
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
  }
  return memo[n];
};

// 迭代
function fib (n) {
  if (n <= 1) {
    return n;
  }

  let first = 1;
  let second = 2;

  for (let i = 3; i <= n; i++) {
    let thrid = first + second;

    first = second;
    second = thrid;
  }

  return second;
};

路径计算问题（二维）

// opt[i, j] = opt[i + 1, j] + opt[i, j + 1]

// 递推伪代码，状态转移方程（DP 方程、动态规划方程）
if (a[i, j] === 'blank') {
  opt[i, j] = opt[i + 1, j] + opt[i, j + 1]
} else {
  opt[j, j] = 0;
}

总结

• 打破思维习惯，形成机器思维
• 理解复杂逻辑的关键

MIT 动态规划课程最短路径算法

动态规划关键点

• 最优子结构： opt[n] = best_of(opt[n - 1], opt[n - 2], ...)
• 存储中间状态： opt[i]
• 递推公式（状态转移方程或 DP 方程）
  • Fib：opt[i] = opt[n - 1] + opt[n - 2]
  • 二维路径：opt[i, j] = opt[i + 1, j] + opt[i, j + 1]

相关题目

不同路径 （Facebook、亚马逊、微软在半年内面试中考过）

不同路径 II （谷歌、美团、微软在半年内面试中考过）

最长公共子序列（字节跳动、谷歌、亚马逊在半年内面试中考过）

// 不同路径

/**
 * 自底向上
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function(m, n) {
  const dp = new Array(m).fill(0).map(() => new Array(n).fill(0));

  for (let i = m - 1; i >= 0; i--) {
    for (let j = n - 1; j >= 0; j--) {
      if (i == m - 1 || j == n - 1) {
        dp[i][j] = 1;
      } else {
        dp[i][j] = dp[i + 1][j] + dp[i][j + 1];
      }
    }
  }

  return dp[0][0];
};

/**
 * 自顶向下
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function(m, n) {
  const dp = new Array(m).fill(0).map(() => new Array(n).fill(0));

  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (i == 0 || j == 0) {
        dp[i][j] = 1;
      } else {
        dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
      }
    }
  }

  return dp[m - 1][n - 1];
};


/**
 * 算法优化
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function(m, n) {
  const dp = new Array(m).fill(0).map(() => new Array(n).fill(0));

  for (let i = 0; i < m; i++) {
    dp[i][0] = 1;
  }
  for (let i = 0; i < n; i++) {
    dp[0][i] = 1;
  }
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
    }
  }

  return dp[m - 1][n - 1];
};

// 不同路径Ⅱ

/**
 * @param {number[][]} obstacleGrid
 * @return {number}
 */
var uniquePathsWithObstacles = function(obstacleGrid) {
  const m = obstacleGrid.length,
        n = obstacleGrid[0].length;
        
  const dp = new Array(m).fill(0).map(() => new Array(n).fill(0));

  for (let i = 0; i < m && obstacleGrid[i][0] === 0; i++) {
    dp[i][0] = 1;
  }
  for (let i = 0; i < n && obstacleGrid[0][i] === 0; i++) {
    dp[0][i] = 1;
  }
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      if (obstacleGrid[i][j] == 1) {
        dp[i][j] = 0;
      } else {
        dp[i][j] = dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
      }
    }
  }

  return dp[m - 1][n - 1];
};

// 最长公共子序列

// s1  s2
// if (s1[length - 1] != s2[s2.length - 1]) lcs[s1, s2] = max(lcs[s1 - 1, s2], lcs[s1, s2 - 1]);
// 	lcs[s1, s2] = max(lcs[s1 - 1, s2], lcs[s1, s2 - 1], lcs[s1 - 1, s2 - 1])
// if (s1[length - 1] == s2[s2.length - 1]) lcs[s1, s2] = lcs[s1 - 1, s2 - 1] + 1
//  lcs[s1, s2] = max(lcs[s1 - 1, s2], lcs[s1, s2 - 1], lcs[s1 - 1, s2 - 1], lcs[s1 -1, s2 - 1] + 1)

=>

// if (s1[length - 1] != s2[s2.length - 1]) lcs[s1, s2] = max(lcs[s1 - 1, s2], lcs[s1, s2 - 1]);
// if (s1[length - 1] == s2[s2.length - 1]) lcs[s1, s2] = lcs[s1 - 1, s2 - 1] + 1

/**
 * @param {string} text1
 * @param {string} text2
 * @return {number}
 */
var longestCommonSubsequence = function(text1, text2) {
  const m = text1.length,
        n = text2.length;
  
  const dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));

  for (let i = 1; i <= m; i++) {
    const c1 = text1[i - 1];

    for (let j = 1; j <= n; j++) {
      const c2 = text2[j - 1];

      if (c1 == c2) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }

  return dp[m][n];
};

爬楼梯（阿里巴巴、腾讯、字节跳动在半年内面试常考）

三角形最小路径和（亚马逊、苹果、字节跳动在半年内面试考过）

最大子序和（亚马逊、字节跳动在半年内面试常考）

乘积最大子数组（亚马逊、字节跳动、谷歌在半年内面试中考过）

零钱兑换（亚马逊在半年内面试中常考）

打家劫舍（字节跳动、谷歌、亚马逊在半年内面试中考过）

打家劫舍 II （字节跳动在半年内面试中考过）

买卖股票的最佳时机（亚马逊、字节跳动、Facebook 在半年内面试中常考）

买卖股票的最佳时机 II （亚马逊、字节跳动、微软在半年内面试中考过）

买卖股票的最佳时机 III （字节跳动在半年内面试中考过）

最佳买卖股票时机含冷冻期（谷歌、亚马逊在半年内面试中考过）

买卖股票的最佳时机 IV （谷歌、亚马逊、字节跳动在半年内面试中考过）

买卖股票的最佳时机含手续费

股票问题系列通解https://leetcode-cn.com/circle/article/qiAgHn/

高级 DP 题目

完全平方数（亚马逊、谷歌在半年内面试中考过）

编辑距离 （重点）

跳跃游戏（亚马逊在半年内面试中考过）

跳跃游戏 II （亚马逊、华为字节跳动在半年内面试中考过）

不同路径（Facebook、亚马逊、微软在半年内面试中考过）

不同路径 II （谷歌、美团、微软在半年内面试中考过）

不同路径 III （谷歌在半年内面试中考过）

零钱兑换（亚马逊在半年内面试中常考）

零钱兑换 II （亚马逊、字节跳动在半年内面试中考过）