如果你问一个算法竞赛选手“最怕什么”，答案很可能不是红黑树，不是网络流，而是——动态规划。
动态规划（Dynamic Programming，简称DP）有一种独特的魔力：你觉得自己学会了，换个题目又不会了；你对着题解看了三遍，觉得自己懂了，关上题解写出了一堆漏洞百出的代码；你终于AC了一道题，满怀信心地去做下一道，发现连状态定义都找不到头绪。
这不是你一个人的困境。DP被公认为是算法面试和竞赛中最难掌握的知识点之一。但如果你愿意沉下心来，你会发现DP其实是有规律可循的。本文将带你系统梳理六种经典的DP模型，帮助你在“入门”和“自闭”之间找到一条相对平坦的路。
一、背包DP：最经典的入门模型
背包问题是大多数人的DP启蒙老师。它的核心思想很简单：在有限的总容量下，如何选择物品使得价值最大？
0/1背包是所有背包问题的基础。每个物品只有选或不选两种状态。状态定义为dp[i][j]表示前i个物品放入容量为j的背包中所能获得的最大价值，转移方程为：
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])
空间可以优化为一维数组，但要注意内层循环必须倒序——这个细节让无数初学者踩过坑。
完全背包则允许每个物品无限次选取，转移方程几乎一样，只是内层循环变成了正序。而多重背包介于两者之间，每个物品有有限个，可以通过二进制拆分转化为0/1背包求解。
背包DP之所以适合入门，是因为它的状态定义和转移都非常直观。当你理解了背包问题，你就理解了动态规划最核心的两个要素：状态和转移。
二、线性DP：最直接的递推思维
线性DP是指在一条线上进行决策的DP问题，通常以一维或二维数组作为状态。它最接近我们理解的“递推”概念。
最长上升子序列（LIS）是线性DP的典型代表。状态dp[i]表示以第i个元素结尾的最长上升子序列长度，转移时需要遍历前面所有比当前元素小的位置：
dp[i] = max(dp[j]) + 1, 其中 j < i 且 a[j] < a[i]
这个O(n²)的解法写起来很简单，但真正让人“哇塞”的是O(n log n)的贪心+二分优化版本——用了一个辅助数组维护不同长度下的最小末尾值。
最长公共子序列（LCS）则是二维线性DP的代表。dp[i][j]表示字符串A的前i个字符和字符串B的前j个字符的LCS长度，转移时根据当前字符是否相等分情况讨论。
线性DP的美妙之处在于它的状态转移图往往是一个有向无环图（DAG），你只需要按照某种顺序（比如从左到右、从上到下）遍历即可。这也引出了一个重要结论：能用DP解决的问题，往往都可以转化为DAG上的最短/最长路径问题。
三、区间DP：化整为零的合并思维
区间DP处理的是“区间上的最优解”问题。它的核心思想是：大区间的最优解可以由其内部的子区间合并得到。
状态通常定义为dp[i][j]表示区间[i, j]上的最优值，转移时枚举区间内的分割点k：
dp[i][j] = min(dp[i][k] + dp[k+1][j] + cost(i, j, k))
矩阵链乘是区间DP的经典案例。给定一系列矩阵，不同的乘法顺序会导致截然不同的计算量，问题是要找到计算量最小的顺序。
石子合并问题则更加直观：把N堆石子合并成一堆，每次只能合并相邻的两堆，代价是两堆石子数量之和，求最小总代价。
区间DP有一个很重要的技巧：按区间长度从小到大进行递推。因为计算大区间时需要用到小区间的结果，所以循环的顺序是：先枚举区间长度，再枚举区间起点，最后枚举分割点。
很多初学者第一次接触区间DP时会感到不适——因为它打破了“从左到右”的直觉。但当你真正理解了“分而治之”的思想，区间DP其实比线性DP更加优雅。
四、树形DP：在树上做决策
当问题结构从“线”变成“树”时，线性DP就不够用了。树形DP应运而生——它是在树结构上进行的动态规划，通常采用深度优先搜索（DFS）的后序遍历来完成。
没有上司的舞会是树形DP的入门题。公司里每个人都有一个直属上司，员工和直属上司不能同时参加舞会，每个人有一个快乐值，问最大总快乐值。
状态定义是树形DP的经典设计：dp[u][0]表示不选择节点u时的最优值，dp[u][1]表示选择节点u时的最优值。转移时，如果选择了u，则其子节点都不能选；如果不选u，子节点可选可不选。
树形DP的精髓在于：先处理子树，再处理当前节点。这种“从下往上”的信息传递完美契合了树的递归结构。
更复杂的树形DP还会涉及“树上背包”，即在树的每个节点上做背包决策。例如“树形依赖背包”问题中，选择了父节点才能选择子节点，这会导致一些有趣的约束条件。
五、状态压缩DP：用二进制玩转集合
当状态维度太多时，传统的多维数组会面临“维度爆炸”的问题。状态压缩DP用二进制数来表示状态集合，将指数级别的状态压缩进一个整数里。
旅行商问题（TSP）是最典型的状态压缩DP例子。你要从某个城市出发，经过所有城市恰好一次，最后回到起点，求最短路径。如果不压缩状态，你需要记录“已经访问过的城市集合”和“当前所在城市”，这显然不是一个简单的低维数组能表达的。
状态定义为dp[mask][i]，其中mask是一个二进制数，第j位为1表示城市j已经访问过，i表示当前所在的城市。转移时从已访问集合中扩展到一个未访问的城市。
状态压缩DP最大的挑战有两个：一是理解二进制运算（与、或、非、移位），二是处理复杂的状态转移逻辑。但它的魅力在于，你可以在2^n的复杂度内解决n≤20左右的集合类问题——这对于暴力枚举来说是不可能的。
一个常用的优化技巧是预处理：提前计算出所有合法状态之间的转移代价，避免在DP过程中重复计算。
六、数位DP：拆位计算的精妙艺术
数位DP解决的是“统计区间内满足某种性质的数字个数”这类问题。例如：求[1, N]中不包含连续数字“13”的数有多少个。
数位DP的核心思想是按位处理。我们先把数字拆成各个数位，然后从高位到低位逐位决策，同时用状态记录“到目前为止是否已经满足条件”以及“是否已经贴紧上界”。
状态通常包含三个维度：pos表示当前处理到第几位，state表示一些与问题相关的状态（比如前面是否已经出现了13），limit表示前面的位是否与上界完全相同（决定了当前位置的可选范围）。
数位DP有一个非常有用的技巧：用记忆化搜索代替手动迭代。写一个递归函数dfs(pos, state, limit)，在递归过程中枚举当前位的数字，递归调用下一层，最后记忆化返回结果。这样做不仅代码清晰，而且不容易出错。
数位DP的优雅之处在于它把复杂的区间统计问题分解成了逐位决策的组合问题。虽然写起来有点绕，但一旦掌握了“limit”这个状态的含义，你就会发现它其实非常套路化。
从入门到“自闭”再到“通透”
回顾这六种DP模型，你会发现它们有一个共同的结构：定义状态、写出转移、确定边界、选择遍历顺序。
初学DP时，大多数人会经历这样一个过程：
-
第一阶段：连状态都不会定义，看到题目大脑一片空白。
-
第二阶段：照着题解能写出来，换一道题又不会了。
-
第三阶段：能识别出题目属于哪种模型，但转移方程写不对。
-
第四阶段：能独立解决常规DP题，但遇到变体还是会卡住。
-
第五阶段：真正理解了DP的本质是一种“空间换时间”的暴力枚举，能够根据问题结构自创状态和转移。
从第一阶段到第五阶段，没有捷径，唯一的办法就是多做题、多总结、多思考。但有一点可以让你少走弯路：不要盲目刷题，而是在做完每道题之后，问自己三个问题——
-
这道题的状态为什么这样定义？还有其他定义方式吗？
-
转移方程的本质是什么？它对应了问题中的什么决策？
-
这道题的模型属于本文介绍的哪一种？或者它结合了多种模型？
动态规划之所以让人“从入门到自闭”，是因为它不像排序算法那样有固定的写法，也不像数据结构那样有明确的模板。它更像是一种思维方式——一种把大问题拆解成小问题、用小问题的答案组合出大问题答案的思维方式。
当你真正理解了这种思维，你就会发现：DP不是背模板，而是讲故事。状态是故事的主人公，转移是故事的剧情推进，边界条件是故事的起点，最终答案是故事的结局。
愿你早日从“自闭”走向“通透”。毕竟，动态规划的英文缩写是DP，也有人把它戏称为“Diu Ping”——别灰心，继续丢平焦虑，一步步来，你终将翻越这座算法之山。 |
