SorryToPerson logo
返回
算法2026-04-15·8 分钟

算法知识库：动态规划实现

常见动态规划问题及状态转移思路的 JavaScript/TypeScript 实现。

动态规划实现

1. 动态规划核心思想

时间复杂度: 取决于具体问题，通常 O(n) 到 O(n²) 空间复杂度: O(n) 到 O(n²)，可优化到 O(1) 或 O(n)

  • 将问题拆分成子问题。
  • 使用状态数组保存中间结果。
  • 避免重复计算。

2. 斐波那契数列

时间复杂度: O(n) 空间复杂度: O(n)

ts
function fibonacci(n: number): number {
  if (n < 2) return n;
  const dp = [0, 1];
  for (let i = 2; i <= n; i += 1) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}

3. 最长公共子序列（LCS）

时间复杂度: O(mn) 空间复杂度: O(mn)

ts
function longestCommonSubsequence(text1: string, text2: string): number {
  const m = text1.length;
  const n = text2.length;
  const dp: number[][] = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));

  for (let i = 1; i <= m; i += 1) {
    for (let j = 1; j <= n; j += 1) {
      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];
}

4. 最小路径和

ts
function minPathSum(grid: number[][]): number {
  const rows = grid.length;
  const cols = grid[0].length;
  const dp: number[][] = Array.from({ length: rows }, () => Array(cols).fill(0));

  dp[0][0] = grid[0][0];
  for (let i = 1; i < rows; i += 1) dp[i][0] = dp[i - 1][0] + grid[i][0];
  for (let j = 1; j < cols; j += 1) dp[0][j] = dp[0][j - 1] + grid[0][j];

  for (let i = 1; i < rows; i += 1) {
    for (let j = 1; j < cols; j += 1) {
      dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
    }
  }

  return dp[rows - 1][cols - 1];
}

5. 实现要点

  • 明确状态定义和状态转移方程。
  • 优化空间可使用滚动数组。
  • 适合具有重叠子问题和最优子结构的问题。
算法动态规划JavaScript