常见问题与技巧

易错点

这些是 DP 中的常见陷阱和高级技巧。

---

一、初始化问题

dp[0] 还是 dp[1]？

// 情况1: dp[i] 表示前 i 个元素（i 从 1 开始）
const dp = Array(n + 1).fill(0);
dp[0] = 0;  // 空集合
dp[1] = ...;

// 情况2: dp[i] 表示以 i 结尾的元素（i 从 0 开始）
const dp = Array(n).fill(...);
dp[0] = ...;

// 错误示例
const dp = Array(n).fill(0);
// dp[0] = ??? 容易忘记

边界检查

// ❌ 错误
for (let i = 1; i <= n; i++) {
  dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i-1]); // i-2 可能为负
}

// ✅ 正确
for (let i = 1; i <= n; i++) {
  if (i === 1) {
    dp[i] = ...;
  } else {
    dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i-1]);
  }
}

// ✅ 或者用特殊值
dp[1] = -Infinity; // i=1 时不能从 i-2 转移

---

二、遍历顺序问题

0/1 背包 vs 完全背包

// 0/1 背包 - 倒序（保证每件物品只选一次）
for (let i = 0; i < n; i++) {
  for (let j = W; j >= weights[i]; j--) {
    dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
  }
}

// 完全背包 - 正序（每件物品可选无限次）
for (let i = 0; i < n; i++) {
  for (let j = weights[i]; j <= W; j++) {
    dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
  }
}

// 多重背包 - 枚举次数
for (let i = 0; i < n; i++) {
  for (let j = W; j >= weights[i]; j--) {
    for (let k = 1; k <= count[i]; k++) {
      if (j >= k * weights[i]) {
        dp[j] = Math.max(dp[j], dp[j - k * weights[i]] + k * values[i]);
      }
    }
  }
}

二维 DP 的遍历顺序

// 情况1: dp[i][j] 只依赖 dp[i-1][*] 和 dp[i][j-1]
// → 按行遍历，正序
for (let i = 1; i <= m; i++) {
  for (let j = 1; j <= n; j++) {
    dp[i][j] = ...;
  }
}

// 情况2: dp[i][j] 依赖 dp[i-1][j-1]（如 LCS）
// → 任意顺序，只要不覆盖即可
for (let i = 1; i <= m; i++) {
  for (let j = 1; j <= n; j++) {
    if (s1[i-1] === s2[j-1]) {
      dp[i][j] = dp[i-1][j-1] + 1;
    }
  }
}

// 情况3: 区间 DP
// → 按长度从小到大
for (let len = 2; len <= n; len++) {
  for (let i = 0; i + len - 1 < n; i++) {
    const j = i + len - 1;
    // ...
  }
}

---

三、空间优化技巧

一维滚动数组

// 二维 dp
const dp: number[][] = Array.from({ length: m + 1 }, () =>
  Array(n + 1).fill(0)
);

// 优化成一维
let dp = Array(n + 1).fill(0);
for (let i = 1; i <= m; i++) {
  // 从右往左遍历（0/1背包）
  for (let j = n; j >= 0; j--) {
    dp[j] = ...; // dp[i-1][j] 变成 dp[j]
  }
}

行状态压缩

// 路径 DP - 只需要上一行
let prev = Array(n).fill(0);
let curr = Array(n).fill(0);

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

更进一步 - 单数组原地修改

let dp = Array(n + 1).fill(0);

// 处理第一行/第一列
for (let j = 1; j <= n; j++) dp[j] = j;

// 处理其他位置
for (let i = 2; i <= m; i++) {
  for (let j = 1; j <= n; j++) {
    if (condition) {
      dp[j] = newValue;
    }
    // 注意：此时 dp[j-1] 已经是第 i 行的值
  }
}

---

四、状态定义技巧

多状态

// 股票问题 - 三状态
// dp[i][0] = 不持有
// dp[i][1] = 持有
// dp[i][2] = 冷冻期

// 打家劫舍 II - 首位相连
// dp[i][0] = 不抢第 i 家
// dp[i][1] = 抢第 i 家
// 分两种情况：抢头不抢尾 / 抢尾不抢头

// 粉刷房子 - 相邻颜色不同
// dp[i][j] = 前 i 个房子，第 i 个颜色为 j 的最小代价

降维状态

// ❌ 复杂状态
dp[i][j][k][l] // 四维

// ✅ 降维思考
// 观察哪些维度是必须的，哪些可以压缩
// 例：背包问题中，重量和价值是必须的
//     但 "是否已经访问" 可以用 mask 表示

---

五、特殊处理

处理负数和零

// 乘积最大子数组 - 必须同时记录 max 和 min
let maxProd = nums[0];
let minProd = nums[0];
let ans = nums[0];

for (let i = 1; i < n; i++) {
  const mx = maxProd, mn = minProd;
  maxProd = Math.max(mx * nums[i], mn * nums[i], nums[i]);
  minProd = Math.min(mx * nums[i], mn * nums[i], nums[i]);
  ans = Math.max(ans, maxProd);
}

处理大数

// 方法1: BigInt
const dp = Array(n).fill(BigInt(0));

// 方法2: 取模
const MOD = 1e9 + 7;
dp[i] = (dp[i] + something) % MOD;

// 方法3: 对数压缩（乘积变加法）
dp[i] = Math.log(value);

---

六、调试技巧

打印 DP 表

function printDP(dp: number[][]) {
  for (const row of dp) {
    console.log(row.map(v => v.toString().padStart(3)).join(' '));
  }
}

检查转移

function debug() {
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      const old = dp[i][j];
      // 计算新值
      dp[i][j] = ...;
      if (old !== dp[i][j]) {
        console.log(`dp[${i}][${j}]: ${old} -> ${dp[i][j]}`);
      }
    }
  }
}

---

七、常见变形

环形结构

// 打家劫舍 II - 首尾相连
// 分两种情况：
// 1. 不抢第一家：dp[1] = 0, 计算 2...n
// 2. 不抢最后一家：dp[0] = 0, 计算 1...n-1

// 取最大值

多维转移

// 例：一和零（两个约束）
// dp[i][j][k] = 前 t 个字符串，j 个 0，k 个 1
// 空间优化：dp[j][k] 滚动

路径计数带障碍

function uniquePathsWithObstacles(grid: number[][]): number {
  const m = grid.length, n = grid[0].length;
  const dp = Array(n).fill(0);
  dp[0] = grid[0][0] === 0 ? 1 : 0;

  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j] === 1) {
        dp[j] = 0; // 障碍物
      } else if (j > 0) {
        dp[j] += dp[j - 1]; // 只累加左边
      }
    }
  }

  return dp[n - 1];
}

---

参见: **DP算法索引** | **刷题指南**