跳到主要内容

动态规划✅

因数分解​

如下，实现 calc 方法，可以将输入的数拆解为尽可能多的乘数，所有数相乘等于输入数。

/**
 * @param {number} n 乘积
 * @return {Array} 拆解后的乘数
 * input: 7
 * output: [7]
 * input: 8
 * output: [2, 2, 2]
 * input: 24
 * output: [2, 2, 2, 3]
 */

function calc (n) { }

爬楼梯​

/**
 * 爬楼 n 阶你, 每次可以爬 1 或 2 个台阶。有多少种不同的方法可以爬到楼顶
 * 输入：2
 * 输出：2
 * 1. 1 步 + 1 步
 * 2. 2 步
 * 输入：3
 * 输出：3
 * 1. 1 步 + 1 步 + 1 步
 * 2. 1 步 + 2 步
 * 3. 2 步 + 1 步
 */
function climbStairs (n) {

}
答案
function climbStairs (n) {
  if (n === 0) { return 0 }
  if (n === 1) return 1
  if (n === 2) return 2
  return climbStairs(n - 1) + climbStairs(n - 2)
}

module.exports = climbStairs

Open browser consoleTests

斐波那契数列​

/**
 * 斐波那契数列
 * 输入：n = 5
 * 输出：5
 * 解释：斐波那契数列为 0, 1, 1, 2, 3, 5, 8, ...
 */
function fibonacci (n) {

}
答案
function fibonacci (n) {
  if (n <= 1) return n
  let prev = 0; let curr = 1
  for (let i = 2; i <= n; i++) {
    [prev, curr] = [curr, prev + curr]
  }
  return curr
}

module.exports = fibonacci

Open browser consoleTests

最长递增子序列​

/**
 * 最长递增子序列
 * 输入：[10,9,2,5,3,7,101,18]
 * 输出：4
 * 解释：最长上升子序列是 [2,3,7,101]，长度为 4
 */
function lengthOfLIS (nums) {

}
答案
function lengthOfLIS (nums) {
  // 如果输入数组为空，返回0，因为没有子序列
  if (nums.length === 0) return 0

  // 创建一个DP数组，初始化为1，因为任何元素的最小LIS（最长递增子序列）为1（它本身）
  const dp = new Array(nums.length).fill(1)

  // 从数组的第二个元素开始迭代
  for (let i = 1; i < nums.length; i++) {
    // 对于每个元素，检查所有之前的元素
    for (let j = 0; j < i; j++) {
      // 如果当前元素大于某个之前的元素
      if (nums[i] > nums[j]) {
        // 更新当前元素的DP值为其当前值或之前元素的DP值加1中的较大值
        dp[i] = Math.max(dp[i], dp[j] + 1)
      }
    }
  }

  // 返回DP数组中的最大值，表示LIS的长度
  return Math.max(...dp)
}

module.exports = lengthOfLIS

Open browser consoleTests

延伸阅读

在 Vue 等框架的 diff 算法中，也会使用最长递增子序列来优化 diff 逻辑。其中 Vue 的最长递增子序列源码如下 getSequence

编辑距离​

/**
 * 编辑距离
 * 输入：word1 = "horse", word2 = "ros"
 * 输出：3
 * 解释：
 * horse -> rorse (将 'h' 替换为 'r')
 * rorse -> rose (删除 'r')
 * rose -> ros (删除 'e')
 */
function minDistance (word1, word2) {

}
答案
function minDistance (word1, word2) {
  const m = word1.length; const n = word2.length
  const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0))
  for (let i = 0; i <= m; i++) dp[i][0] = i
  for (let j = 0; j <= n; j++) dp[0][j] = j
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; 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] + 1, dp[i - 1][j - 1] + 1)
      }
    }
  }
  return dp[m][n]
}

module.exports = minDistance

Open browser consoleTests

背包问题​

/**
 * 背包问题
 * 输入：weights = [2, 3, 4, 5], values = [3, 4, 5, 6], capacity = 5
 * 输出：7
 * 解释：选择物品 1 (重量 2, 价值 3) 和物品 2 (重量 3, 价值 4)，总价值 7
 */
function knapsack (weights, values, capacity) {

}
答案
function knapsack (weights, values, capacity) {
  const n = weights.length
  const dp = Array.from({ length: n + 1 }, () => Array(capacity + 1).fill(0))
  for (let i = 1; i <= n; i++) {
    for (let w = 1; w <= capacity; w++) {
      if (weights[i - 1] <= w) {
        dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1])
      } else {
        dp[i][w] = dp[i - 1][w]
      }
    }
  }
  return dp[n][capacity]
}

module.exports = knapsack

Open browser consoleTests

路径规划​

答案

核心概念 LeetCode 第 62 题（不同路径 / Unique Paths）： 机器人位于一个 $m \times n$ 网格的左上角 $(0, 0)$，每次只能向右或向下移动一步，求到达右下角 $(m-1, n-1)$ 共有多少条不同的路径：

  1. 状态定义：设 $dp[i][j]$ 表示到达网格 $(i, j)$ 位置的不同路径数。
  2. 状态转移方程：由于只能从上方或左方到达该格，故 $dp[i][j] = dp[i - 1][j] + dp[i][j - 1]$。
  3. 边界条件：第一行与第一列的任意格子都只有 1 种走法（一直向右或一直向下），即 $dp[0][j] = 1, dp[i][0] = 1$。
  4. 空间优化（滚动数组）：$dp[j]$ 仅依赖本行的左侧值和上一行的同列值，可用长度为 $n$ 的一维数组完成状态压缩。

代码实现（一维滚动数组最优解）：

function uniquePaths (m, n) {
  // 初始化一维 dp 数组，首行所有格子路径数均为 1
  const dp = new Array(n).fill(1)

  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      // 当前格子路径 = 原上一行同列值(dp[j]) + 本行左侧值(dp[j-1])
      dp[j] = dp[j] + dp[j - 1]
    }
  }

  return dp[n - 1]
}

// 验证
console.log(uniquePaths(3, 7)) // 28
console.log(uniquePaths(3, 2)) // 3

复杂度分析

  • 时间复杂度：$O(m \times n)$，双重循环遍历网格。
  • 空间复杂度：$O(n)$，仅需一行长度为 $n$ 的数组空间。

面试官视角

  • 考查从基础的二维矩阵 DP 推导，下探到空间压缩降维（一维滚动数组）的能力；数学背景好的候选人还可指出利用组合数学公式 C(m+n-2, m-1) = (m+n-2)! / ((m-1)!(n-1)!) 直接在 $O(\min(m, n))$ 时间内计算完成。

200. 岛屿数量**​

  • 难度：中等
  • 考点：DFS、BFS
  • 应用场景：图形处理、连通性问题

dfs

function numIslands (grid: string[][]): number {
  if (grid.length === 0) return 0

  const rows = grid.length
  const cols = grid[0].length
  let count = 0

  // DFS遍历整个岛屿并标记
  const dfs = (row: number, col: number) => {
    // 边界检查或已访问（水域）
    if (row < 0 || row >= rows || col < 0 || col >= cols || grid[row][col] === '0') {
      return
    }

    grid[row][col] = '0'

    // 四个方向DFS
    dfs(row - 1, col) // 上
    dfs(row + 1, col) // 下
    dfs(row, col - 1) // 左
    dfs(row, col + 1) // 右
  }

  // 遍历网格
  for (let row = 0; row < rows; row++) {
    for (let col = 0; col < cols; col++) {
      if (grid[row][col] === '1') {
        count++
        dfs(row, col)
      }
    }
  }

  return count
}