跳到主要内容

动态规划✅

因数分解​

如下，实现 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

路径规划​

/*
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角。
问总共有多少条不同的路径？
输入：m = 3, n = 7
输出：28
*/

function uniquePaths (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
}
22%