DP 优化 (Optimization Techniques)

[!abstract] 当基础 DP 复杂度太高时，使用优化技巧将 O(n²) 或更高降到 O(n log n) 或 O(n)。

---

优化方法总览

优化方法	适用场景	复杂度
空间优化	一维/二维滚动	O(n) → O(1)
单调队列	滑动窗口最值	O(n)
斜率优化	决策单调性	O(n)
二分优化	LIS 等	O(n log n)
矩阵加速	线性递推	O(n³ log k)
分治优化	凸包/四边形	O(n log n)

---

1. 空间优化

一维滚动数组

// 原始二维 dp
const dp: number[][] = Array.from({ length: n + 1 }, () =>
  Array(m + 1).fill(0)
);
for (let i = 1; i <= n; i++) {
  for (let j = 0; j <= m; j++) {
    dp[i][j] = ...;
  }
}

// 空间优化 - 只保留需要的行
let prev: number[] = Array(m + 1).fill(0);
let curr: number[] = Array(m + 1).fill(0);

for (let i = 1; i <= n; i++) {
  [prev, curr] = [curr, prev]; // 交换
  curr.fill(0);
  for (let j = 0; j <= m; j++) {
    curr[j] = ...;
  }
}

进一步优化

// 只用一个数组（倒序遍历避免覆盖）
const dp: number[] = Array(m + 1).fill(0);

for (let i = 1; i <= n; i++) {
  // 0/1 背包：倒序
  for (let j = m; j >= weights[i]; j--) {
    dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
  }

  // 完全背包：正序
  // for (let j = weights[i]; j <= m; j++) { ... }
}

---

2. 单调队列优化

适用场景

• dp[i] = min/max(dp[j] + cost(j, i))，其中 j 在滑动窗口内

经典问题：染色法站位

function shortestDistance(color: number[][]): number[] {
  const n = color[0].length;
  const INF = Infinity;
  const dp: number[][] = Array.from({ length: color.length }, () =>
    Array(n).fill(INF)
  );

  // 第一栋房子
  dp[0] = Array(n).fill(0);

  for (let i = 1; i < color.length; i++) {
    const dq: number[] = [];

    for (let j = 0; j < n; j++) {
      // 维护单调队列：dp[i-1][j] - j（斜率）
      while (dq.length > 0 && dp[i - 1][dq[dq.length - 1]] <= dp[i - 1][j]) {
        dq.pop();
      }
      dq.push(j);

      // 移除不在窗口的
      while (dq.length > 0 && dq[0] + n <= j) {
        dq.shift();
      }

      // 取最小值
      dp[i][j] = dp[i - 1][dq[0]] + Math.abs(color[i][j] - color[i - 1][dq[0]]);
    }
  }

  return dp[dp.length - 1];
}

滑动窗口模板

function monotonicQueueOptimize(dp: number[], k: number): number[] {
  const dq: number[] = []; // 存索引
  const result: number[] = [];

  for (let i = 0; i < dp.length; i++) {
    // 1. 维护单调性 - 移除比当前元素大的
    while (dq.length > 0 && dp[dq[dq.length - 1]] >= dp[i]) {
      dq.pop();
    }
    dq.push(i);

    // 2. 移除过期元素（窗口外）
    while (dq.length > 0 && dq[0] <= i - k) {
      dq.shift();
    }

    // 3. 取最值
    if (i >= k - 1) {
      result.push(dp[dq[0]]);
    }
  }

  return result;
}

---

3. 斜率优化

适用场景

• dp[i] = min(dp[j] + (slope_j) * i + b_j)
• 决策点 j 的斜率单调

公式推导

dp[i] = min(dp[j] + cost(i, j))
      = min(dp[j] + A[i] * B[j])  // 假设

设 line_j(x) = dp[j] + B[j] * x
则 dp[i] = min(line_j(A[i]))

经典问题：玩具装箱

function toyStorage(n: number, C: number, lengths: number[]): number {
  // 前缀和
  const prefix = Array(n + 1).fill(0);
  for (let i = 1; i <= n; i++) {
    prefix[i] = prefix[i - 1] + lengths[i - 1];
  }

  // 转换: x_j = prefix[j], w_i = prefix[i] + i
  // dp[i] = dp[j] + (w_i - x_j)^2
  //       = dp[j] + w_i^2 - 2*w_i*x_j + x_j^2

  const x = Array(n + 1).fill(0);
  for (let i = 1; i <= n; i++) {
    x[i] = prefix[i] + i;
  }

  const dp = Array(n + 1).fill(0);
  const dq: number[] = [0]; // 下标队列

  // 判断是否需要弹出
  const needPop = (j: number, k: number, i: number): boolean => {
    const slope = (dp: number, j: number) =>
      (dp[j] + x[j] * x[j] - dp[k] - x[k] * x[k]) / (x[j] - x[k]);
    return slope(j, dq[dq.length - 2]) <= slope(dq[dq.length - 2], i);
  };

  const calc = (j: number, i: number): number =>
    dp[j] + (x[i] - x[j]) * (x[i] - x[j]);

  for (let i = 1; i <= n; i++) {
    // 维护凸包上界
    while (dq.length >= 2 && needPop(dq[dq.length - 1], dq[dq.length - 2], i)) {
      dq.pop();
    }

    dp[i] = calc(dq[0], i);

    // 插入新点
    while (dq.length >= 2 &&
           (dp[dq[dq.length - 1]] + x[dq[dq.length - 1]] * x[dq[dq.length - 1]] - dp[dq[dq.length - 2]] - x[dq[dq.length - 2]] * x[dq[dq.length - 2]]) * (x[i] - x[dq[dq.length - 1]]) >=
           (dp[i] + x[i] * x[i] - dp[dq[dq.length - 1]] - x[dq[dq.length - 1]] * x[dq[dq.length - 1]]) * (x[dq[dq.length - 1]] - x[dq[dq.length - 2]])) {
      dq.pop();
    }
    dq.push(i);
  }

  return dp[n];
}

---

4. 二分优化

LIS 的二分优化

function lengthOfLIS(nums: number[]): number {
  const tails: number[] = [];

  for (const num of nums) {
    // 二分查找插入位置
    let left = 0, right = tails.length;
    while (left < right) {
      const mid = (left + right) >> 1;
      if (tails[mid] < num) left = mid + 1;
      else right = mid;
    }

    if (left === tails.length) tails.push(num);
    else tails[left] = num;
  }

  return tails.length;
}

---

5. 矩阵快速幂

适用场景

• 线性递推：dp[i] = a₁dp[i-1] + a₂dp[i-2] + ... + c

function matrixMultiply(A: number[][], B: number[][]): number[][] {
  const n = A.length, m = B[0].length, k = B.length;
  const C: number[][] = Array.from({ length: n }, () => Array(m).fill(0));

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      for (let p = 0; p < k; p++) {
        C[i][j] += A[i][p] * B[p][j];
      }
    }
  }

  return C;
}

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

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

  return result;
}

// 斐波那契: dp[n] = dp[n-1] + dp[n-2]
// 矩阵:
// [dp[n], dp[n-1]]ᵀ = M × [dp[n-1], dp[n-2]]ᵀ
// M = [[1,1], [1,0]]

---

6. 分治优化

适用场景

• DP 满足四边形不等式或单调队列单调性
• dp[i][j] = min(dp[i][k] + dp[k+1][j] + cost(i,j))

function divideConquerDP(
  n: number,
  getCost: (l: number, r: number) => number,
  getOpt: (l: number, r: number) => number // 决策单调
): number[] {
  const dp: number[][] = Array.from({ length: n }, () => Array(n).fill(0));
  const opt: number[][] = Array.from({ length: n }, () => Array(n).fill(0));

  function compute(l: number, r: number, kLo: number, kHi: number) {
    if (l > r) return;

    const mid = (l + r) >> 1;
    let bestK = -1;
    let bestVal = Infinity;

    for (let k = kLo; k <= Math.min(mid, kHi); k++) {
      const val = dp[l][k] + dp[k + 1][mid] + getCost(l, mid);
      if (val < bestVal) {
        bestVal = val;
        bestK = k;
      }
    }

    dp[l][mid] = bestVal;
    opt[l][mid] = bestK;

    compute(l, mid - 1, kLo, bestK);
    compute(mid + 1, r, bestK, kHi);
  }

  compute(0, n - 1, 0, n - 1);
  return dp[0];
}

---

优化选择决策树

---

参见: **DP算法索引** | **基础问题**