手帐 Blog

主题

22 · DP 二维入门 ​

目标：会定义 dp[i][j]；写出不同路径；理解 LCS 状态含义（能写转移即可）。

为什么面试会考 ​

二维 DP 在前端面试里通常点到为止：

  • 网格路径（62）
  • 最长公共子序列（1143）——重在会定义状态，不要求瞬间最优码风

能把二维表「画出来」，比背公式重要。

零基础概念 ​

dp[i][j]：两个维度各自表示进度。

题dp[i][j] 含义（示例）
62走到格子 (i,j) 的路径数
1143text1 前 i 与 text2 前 j 的 LCS 长度

填表顺序：一般从小组到大，依赖「左边 / 上边 / 左上」。

JS 模板：网格 ​

js
const dp = Array.from({ length: m }, () => Array(n).fill(0))
// 初始化第一行 / 第一列
for (let i = 0; i < m; i++) {
  for (let j = 0; j < n; j++) {
    // dp[i][j] = f(dp[i-1][j], dp[i][j-1], ...)
  }
}

精讲题 ​

LeetCode 62. 不同路径 ​

只能向右或向下。dp[i][j] = dp[i-1][j] + dp[i][j-1]。

js
/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function (m, n) {
  const dp = Array.from({ length: m }, () => Array(n).fill(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]
}

第一行、第一列只有一种走法，故初值全 1。

LeetCode 1143. 最长公共子序列 ​

js
/**
 * @param {string} text1
 * @param {string} text2
 * @return {number}
 */
var longestCommonSubsequence = function (text1, text2) {
  const m = text1.length
  const n = text2.length
  const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0))
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (text1[i - 1] === text2[j - 1]) {
        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]
}

相等：左上 + 1；不等：左边与上边取 max。

LeetCode 64. 最小路径和（巩固） ​

js
/**
 * @param {number[][]} grid
 * @return {number}
 */
var minPathSum = function (grid) {
  const m = grid.length
  const n = grid[0].length
  const dp = Array.from({ length: m }, () => Array(n).fill(0))
  dp[0][0] = grid[0][0]
  for (let j = 1; j < n; j++) dp[0][j] = dp[0][j - 1] + grid[0][j]
  for (let i = 1; i < m; i++) dp[i][0] = dp[i - 1][0] + grid[i][0]
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
    }
  }
  return dp[m - 1][n - 1]
}

练习清单 ​

题提示
LeetCode 63. 不同路径 II有障碍格子路径数为 0
LeetCode 72. 编辑距离（可选）三维转移：插删替
LeetCode 5. 最长回文子串中心扩展或区间 DP
LeetCode 221. 最大正方形dp[i][j] 边长

今日验收 ​

  • [ ] 62 能画 3×3 小表手算
  • [ ] 1143 能口述三种转移情况
  • [ ] 二维数组用 Array.from 初始化不会共享引用

若你以前见过 ​

「填表」就是把递归树摊平；面试口述时先说含义，再写两行转移。