动态规划与其他算法

核心区别

理解 DP 与其他算法的边界，什么时候用 DP，什么时候不用。

---

DP vs 分治

相同点

• 都是把问题分解为子问题
• 都是递归求解

不同点

维度	分治	动态规划
子问题	独立的	可能重叠
结果	合并子问题结果	可能复用子问题结果
记忆化	可选	通常必要
示例	归并排序、快速排序	斐波那契、背包

// 分治 - 子问题独立
function mergeSort(arr: number[]): number[] {
  if (arr.length <= 1) return arr;
  const mid = arr.length / 2;
  const left = mergeSort(arr.slice(0, mid));    // 独立
  const right = mergeSort(arr.slice(mid));       // 独立
  return merge(left, right);
}

// DP - 子问题重叠
function fib(n: number, memo: number[] = []): number {
  if (n <= 1) return n;
  if (memo[n]) return memo[n];                    // 复用
  memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
  return memo[n];
}

---

DP vs 贪心

相同点

• 都是求最优解
• 都利用最优子结构

不同点

维度	贪心	动态规划
选择	局部最优	全局最优
回溯	不回溯	可能回溯
最优证明	通常难	一般可证
时间复杂度	通常 O(n)	通常 O(n²) 或更高

贪心失效的例子

// 硬币找零 - 贪心失效
const coins = [1, 3, 4];
// 贪心: 6 = 4 + 1 + 1 = 3枚
// 最优: 6 = 3 + 3 = 2枚

function greedyCoin(coins: number[], amount: number): number {
  let count = 0;
  let remaining = amount;

  // 从大到小选
  for (const coin of [...coins].sort((a, b) => b - a)) {
    while (remaining >= coin) {
      remaining -= coin;
      count++;
    }
  }

  return count;
}

// DP - 正确
function dpCoin(coins: number[], amount: number): number {
  const dp = Array(amount + 1).fill(Infinity);
  dp[0] = 0;

  for (let i = 1; i <= amount; i++) {
    for (const coin of coins) {
      if (i >= coin) {
        dp[i] = Math.min(dp[i], dp[i - coin] + 1);
      }
    }
  }

  return dp[amount];
}

何时用贪心

贪心适用条件

• 问题具有贪心选择性质
• 最优子结构
• 可以证明局部最优 → 全局最优

---

DP vs DFS + 记忆化

本质相同

// 方法1: 自顶向下记忆化
function dfsWithMemo(n: number, memo: number[]): number {
  if (n <= 1) return n;
  if (memo[n]) return memo[n];
  return memo[n] = dfsWithMemo(n - 1, memo) + dfsWithMemo(n - 2, memo);
}

// 方法2: 自底向上 DP
function dpBottomUp(n: number): number {
  const dp = Array(n + 1).fill(0);
  dp[1] = 1;

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

  return dp[n];
}

// 方法3: 空间优化
function dpOptimized(n: number): number {
  let prev2 = 0, prev1 = 1;
  for (let i = 2; i <= n; i++) {
    [prev2, prev1] = [prev1, prev2 + prev1];
  }
  return prev1;
}

区别

维度	DFS+记忆化	自底向上 DP
方向	递归（栈溢出风险）	迭代
顺序	自然顺序	需要确定顺序
初始化	延迟	显式
调试	容易	较难

---

DP vs BFS（最短路）

相同点

• 都可以用于最短路径问题

不同点

维度	BFS	DP
图类型	无权图/有权图	DAG（通常）
状态转移	边	更复杂
队列	需要	不需要

BFS 更适合的场景

// 网格最短路径 - BFS
function shortestPath(grid: number[][], start: [number, number], end: [number, number]): number {
  const queue: [number, number, number][] = [[...start, 0]];
  const visited = new Set();

  while (queue.length > 0) {
    const [x, y, dist] = queue.shift()!;

    if (x === end[0] && y === end[1]) return dist;

    const dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]];
    for (const [dx, dy] of dirs) {
      const nx = x + dx, ny = y + dy;
      if (valid(nx, ny) && !visited.has(`${nx},${ny}`)) {
        visited.add(`${nx},${ny}`);
        queue.push([nx, ny, dist + 1]);
      }
    }
  }

  return -1;
}

// DP 更适合：有权图、有环、状态复杂

---

DP vs 线性代数

递推 → 矩阵加速

// 斐波那契的线性递推
// F(n) = F(n-1) + F(n-2)

// 矩阵形式：
// [F(n), F(n-1)]ᵀ = M × [F(n-1), F(n-2)]ᵀ
// M = [[1, 1], [1, 0]]

function fibMatrix(n: number): number {
  if (n <= 1) return n;

  const M = [[1, 1], [1, 0]];

  // 矩阵快速幂
  function matMul(A: number[][], B: number[][]): number[][] {
    const n = A.length;
    const C: number[][] = Array.from({ length: n }, () => Array(n).fill(0));
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        for (let k = 0; k < n; k++) {
          C[i][j] += A[i][k] * B[k][j];
        }
      }
    }
    return C;
  }

  function matPow(M: number[][], k: number): number[][] {
    const n = M.length;
    let result: number[][] = Array.from({ length: n }, (_, i) =>
      Array(n).fill(0).map((_, j) => i === j ? 1 : 0)
    );
    let base = M;

    while (k > 0) {
      if (k & 1) result = matMul(result, base);
      base = matMul(base, base);
      k >>= 1;
    }

    return result;
  }

  const R = matPow(M, n - 1);
  return R[0][0]; // F(n)
}

---

选择决策树

---

复杂度对照表

算法	时间复杂度	空间复杂度	适用场景
暴力递归	O(2^n)	O(n)	无
记忆化	O(n) ~ O(n²)	O(n)	树形DP
一维DP	O(n) ~ O(n²)	O(1) ~ O(n)	序列DP
二维DP	O(n×m)	O(n×m) 或 O(n)	网格DP
区间DP	O(n³)	O(n²)	合并类
状态压缩	O(n × 2^n)	O(2^n)	集合DP
矩阵加速	O(n³ log k)	O(n²)	线性递推

---

参见: **DP算法索引** | **DP优化**