经典题型汇总

按模式分类

DP 问题虽然千变万化，但核心题型就这几类。

---

一、计数类

爬楼梯/路径计数

// 问题：有多少种方式到达终点？
// 特点：dp[i] = sum(dp[i-1], dp[i-2], ...)

function countWays(n: number, steps: number[]): number {
  const dp = Array(n + 1).fill(0);
  dp[0] = 1;

  for (let i = 1; i <= n; i++) {
    for (const step of steps) {
      if (i >= step) {
        dp[i] += dp[i - step];
      }
    }
  }

  return dp[n];
}

// 应用：
// - 爬楼梯（steps = [1, 2]）
// - 网格路径（dp[i][j] = dp[i-1][j] + dp[i][j-1]）
// - 硬币找零组合数（顺序重要/不重要）

---

二、最值类

斐波那契/最大子段和

// 问题：求最大/最小值
// 特点：dp[i] = max/min(dp[i], dp[i-1] + ...)

function maxSubArray(nums: number[]): number {
  // 最大子序和
  let dp = nums[0];
  let maxAns = dp;

  for (let i = 1; i < nums.length; i++) {
    dp = Math.max(nums[i], dp + nums[i]);
    maxAns = Math.max(maxAns, dp);
  }

  return maxAns;
}

// 变形：
// - 乘积最大子数组（max 和 min 都要记录）
// - 最长递增子序列（dp[i] = max(dp[j] + 1)）

---

三、存在性类

背包/分割

// 问题：能否达到目标？
// 特点：dp[i] = dp[i-a] || dp[i-b] || ...

function canPartition(nums: number[]): boolean {
  const sum = nums.reduce((a, b) => a + b, 0);
  if (sum % 2 !== 0) return false;

  const target = sum / 2;
  const dp = Array(target + 1).fill(false);
  dp[0] = true;

  for (const num of nums) {
    for (let j = target; j >= num; j--) {
      dp[j] = dp[j] || dp[j - num];
    }
  }

  return dp[target];
}

// 应用：
// - 目标和（加法和减法）
// - 能否分成两个等和子集

---

四、序列类

LCS/LIS 问题

// 最长公共子序列
function longestCommonSubsequence(s1: string, s2: string): number {
  const m = s1.length, n = s2.length;
  const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));

  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;
      } else {
        dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
      }
    }
  }

  return dp[m][n];
}

// 最长递增子序列 - 二分优化
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;
}

---

五、路径类

网格/棋盘

// 最小路径和
function minPathSum(grid: number[][]): number {
  const m = grid.length, n = grid[0].length;
  const dp = Array(n).fill(Infinity);
  dp[0] = 0;

  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (j === 0) {
        dp[j] += grid[i][j];
      } else {
        dp[j] = Math.min(dp[j], dp[j - 1]) + grid[i][j];
      }
    }
  }

  return dp[n - 1];
}

// 变形：
// - 带障碍物（障碍处 dp = 0）
// - 三角形（从底向上）
// - 地下城游戏（从右下往左上）

---

六、股票类

状态机 DP

// 通用股票模板（无限次交易）
function maxProfit(prices: number[]): number {
  let dp0 = 0, dp1 = -Infinity;

  for (const price of prices) {
    dp0 = Math.max(dp0, dp1 + price);  // 卖出
    dp1 = Math.max(dp1, dp0 - price);  // 买入
  }

  return dp0;
}

// k 次交易
function maxProfitK(k: number, prices: number[]): number {
  const n = prices.length;
  if (k === 0 || n === 0) return 0;

  const dp = Array(n).fill(0).map(() => Array(2 * k + 1).fill(0));

  for (let j = 1; j < 2 * k; j += 2) {
    dp[0][j] = -prices[0];
  }

  for (let i = 1; i < n; i++) {
    for (let j = 0; j < 2 * k; j += 2) {
      dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j] - prices[i]);
      dp[i][j+1] = Math.max(dp[i-1][j+1], dp[i-1][j] + prices[i]);
    }
  }

  return dp[n-1][2 * k];
}

---

七、区间类

合并/分割

// 合并石子
function minCostMergeStones(stones: number[]): number {
  const n = stones.length;
  const prefix = Array(n + 1).fill(0);
  for (let i = 1; i <= n; i++) {
    prefix[i] = prefix[i - 1] + stones[i - 1];
  }

  const dp = Array.from({ length: n }, () => Array(n).fill(0));

  for (let len = 2; len <= n; len++) {
    for (let i = 0; i + len - 1 < n; i++) {
      const j = i + len - 1;
      dp[i][j] = Infinity;

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

  return dp[0][n - 1];
}

---

八、树形类

树上的选择

// 打家劫舍 III
function rob(root: TreeNode): number {
  const [select, notSelect] = dfs(root);
  return Math.max(select, notSelect);
}

function dfs(node: TreeNode): [number, number] {
  if (!node) return [0, 0];

  const [lSelect, lNotSelect] = dfs(node.left);
  const [rSelect, rNotSelect] = dfs(node.right);

  const select = node.val + lNotSelect + rNotSelect;
  const notSelect = Math.max(lSelect, lNotSelect) + Math.max(rSelect, rNotSelect);

  return [select, notSelect];
}

---

九、状态压缩类

集合枚举

// TSP 旅行商
function travelingSalesman(dist: number[][]): number {
  const n = dist.length;
  const dp: number[][] = Array.from({ length: 1 << n }, () =>
    Array(n).fill(Infinity)
  );
  dp[1][0] = 0;

  for (let mask = 0; mask < (1 << n); mask++) {
    for (let last = 0; last < n; last++) {
      if (dp[mask][last] === Infinity) continue;

      for (let next = 0; next < n; next++) {
        if (!(mask & (1 << next))) {
          const newMask = mask | (1 << next);
          dp[newMask][next] = Math.min(
            dp[newMask][next],
            dp[mask][last] + dist[last][next]
          );
        }
      }
    }
  }

  return Math.min(...dp[(1 << n) - 1]);
}

---

十、字符串类

编辑距离/匹配

// 编辑距离
function minDistance(word1: string, word2: string): number {
  const m = word1.length, n = word2.length;
  const dp: number[][] = Array.from({ length: m + 1 }, (_, i) =>
    Array(n + 1).fill(0).map((_, j) => i === 0 ? j : j === 0 ? i : 0)
  );

  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];
}

---

题型 vs 方法 对应表

题型	特征	方法
计数	多少种方式	累加
最值	最大/最小	max/min
存在性	能否达到	boolean
序列	子串/子序列	双指针
路径	网格/棋盘	方向 DP
股票	买卖交易	状态机
区间	合并/分割	区间 DP
树形	树的遍历	DFS
状态压缩	n≤20	位运算

---

参见: **DP算法索引** | **刷题指南** | **面试真题分类**