📝 写在前面

动态规划的应用极其广泛，不同的问题结构对应不同的 DP 模型。掌握这些经典模型，就像拥有了解决各类优化问题的“武器库”。本文带你系统学习：

• 线性DP：最长上升子序列（LIS）、最长公共子序列（LCS）、最大子段和

• 区间DP：石子合并、矩阵链乘

• 背包问题：0‑1背包、完全背包、多重背包、分组背包

• 树形DP：树上最大独立集、树的直径

• 数位DP：统计数字区间内满足条件的个数

• 状压DP：旅行商问题（TSP）、铺砖问题

• 概率DP：期望问题

每个模型都包含 一句话记住、核心思想、流程图推荐、代码实现、LeetCode实战（附题目链接），让你既能快速理解，又能上手实践。

---

一、线性DP

线性DP是指状态在一条“线”上递推，通常是一维或二维数组，沿着数组下标顺序推进。经典问题有：最长上升子序列（LIS）、最长公共子序列（LCS）、最大子段和。

1️⃣ 最长上升子序列（LIS）

🎯 一句话记住

每个数可以接在前面比它小的数后面，取最长。

🤔 核心思想

定义 dp[i] 为以 nums[i] 结尾的最长上升子序列长度。转移：dp[i] = max(dp[j] + 1)，其中 j < i 且 nums[j] < nums[i]。最后答案取 max(dp)。

优化：贪心 + 二分，时间复杂度 O(n log n)。

📊 流程图

https://cloud.tencent.com/developer/article/1550058

💻 代码实现

// O(n²) 版本
function lengthOfLIS(nums) {
    const n = nums.length;
    const dp = new Array(n).fill(1);
    let maxLen = 1;
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        maxLen = Math.max(maxLen, dp[i]);
    }
    return maxLen;
}

// O(n log n) 贪心+二分
function lengthOfLISOptimized(nums) {
    const tails = [];
    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;
        }
        tails[left] = num;
    }
    return tails.length;
}

🏆 LeetCode实战

• 题目：LeetCode 300. 最长递增子序列

• 题解：见上述代码。

2️⃣ 最长公共子序列（LCS）

🎯 一句话记住

比较两个字符串的字符，相同就斜着加一，不同就取左边或上边的最大值。

🤔 核心思想

定义 dp[i][j] 表示 text1[0..i-1] 和 text2[0..j-1] 的 LCS 长度。转移：

• 若 text1[i-1] == text2[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1

• 否则 dp[i][j] = max(dp[i-1][j], dp[i][j-1])

📊 流程图

• LCS 动画演示（Algorithm Visualizer）

• https://kaoshi.educity.cn/rk/yl9yw37wwn.html

  包含最长公共子序列问题的经典图解（第5个图）

💻 代码实现

function longestCommonSubsequence(text1, text2) {
    const m = text1.length, n = text2.length;
    const dp = Array(m + 1).fill().map(() => Array(n + 1).fill(0));
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            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];
}

🏆 LeetCode实战

• 题目：LeetCode 1143. 最长公共子序列

• 题解：见上述代码。
  
   

  3️⃣ 最大子段和（最大子数组和）

  🎯 一句话记住

  每个数要么自己单独一段，要么接在前面的子段后面，选大的。

  🤔 核心思想

  定义 dp[i] 表示以 nums[i] 结尾的最大子数组和。转移：dp[i] = max(nums[i], dp[i-1] + nums[i])。答案取 max(dp)。

  📊 流程图

• https://cloud.tencent.com/developer/article/1607172

• 💻 代码实现

  function maxSubArray(nums) {
      let maxEndingHere = nums[0];
      let maxSoFar = nums[0];
      for (let i = 1; i < nums.length; i++) {
          maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
          maxSoFar = Math.max(maxSoFar, maxEndingHere);
      }
      return maxSoFar;
  }

  🏆 LeetCode实战

• 题目：LeetCode 53. 最大子数组和

• 题解：见上述代码。

二、区间DP

区间DP是在一个区间上进行递推，通常用 dp[i][j] 表示区间 [i, j] 上的最优值，通过枚举分割点 k 合并左右区间。

1️⃣ 石子合并（典型问题）

🎯 一句话记住

将相邻石子堆合并，每次合并的代价是两堆之和，求总代价最小。

🤔 核心思想

dp[i][j] 表示合并 [i, j] 堆的最小代价。转移：dp[i][j] = min(dp[i][k] + dp[k+1][j] + sum(i,j))，其中 sum(i,j) 是区间和。最后答案为 dp[0][n-1]。

📊 流程图

https://kaoshi.educity.cn/rk/yl9yw37wwn.html

💻 代码实现（以合并石子为例）

function stoneMerge(stones) {
    const n = stones.length;
    const prefix = new Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) prefix[i + 1] = prefix[i] + stones[i];
    const sum = (l, r) => prefix[r + 1] - prefix[l];
    
    const dp = Array.from({ length: n }, () => new Array(n).fill(Infinity));
    for (let i = 0; i < n; i++) dp[i][i] = 0;
    
    for (let len = 2; len <= n; len++) {
        for (let i = 0; i + len - 1 < n; i++) {
            const j = i + len - 1;
            for (let k = i; k < j; k++) {
                dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j] + sum(i, j));
            }
        }
    }
    return dp[0][n - 1];
}

🏆 LeetCode实战

• 题目：LeetCode 上没有直接的“石子合并”，但有一道类似的 LeetCode 312. 戳气球（也是区间DP）。

• 链接：LeetCode 312. 戳气球

• 思路：定义 dp[i][j] 表示戳破 (i, j) 区间内所有气球（不含 i 和 j）的最大硬币数。

2️⃣ 矩阵链乘

🎯 一句话记住

给矩阵序列加括号，使乘法次数最少。

🤔 核心思想

dp[i][j] 表示计算矩阵 i 到 j 的最小乘法次数。转移：dp[i][j] = min(dp[i][k] + dp[k+1][j] + p[i]*p[k+1]*p[j+1])，其中 p 是矩阵维度数组。

📊 流程图

https://kaoshi.educity.cn/rk/yl9yw37wwn.html

💻 代码实现

function matrixChainOrder(p) {
    const n = p.length - 1; // 矩阵个数
    const dp = Array.from({ length: n }, () => new Array(n).fill(Infinity));
    for (let i = 0; i < n; i++) dp[i][i] = 0;
    
    for (let len = 2; len <= n; len++) {
        for (let i = 0; i + len - 1 < n; i++) {
            const j = i + len - 1;
            for (let k = i; k < j; k++) {
                dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j] + p[i] * p[k + 1] * p[j + 1]);
            }
        }
    }
    return dp[0][n - 1];
}

🏆 LeetCode实战

• 题目：LeetCode 上没有直接的矩阵链乘，但可用 LeetCode 312. 戳气球 练习区间DP思想。

📌 面试常见问题

1. 如何判断一个题是线性DP还是区间DP？

   • 如果状态依赖于前一个或几个元素，通常是一维线性DP；如果状态依赖于区间两端，且需要枚举中间点，则是区间DP。

下一期我们将进入背包问题的世界——这是动态规划中最经典的组合优化模型，也是面试和竞赛中的常客。我们将系统学习：

• 0‑1背包：每个物品最多选一次，容量有限，求最大价值

• 完全背包：每个物品无限次使用，求最大价值或组合数

• 多重背包：每个物品有有限个数，用二进制优化

• 分组背包：每组内只能选一个物品，求最大价值

如果你觉得这篇文章对你有帮助，欢迎点赞、收藏、转发