关于DP的一些解题技巧

之前在博客里分享了一些自己写算法题时的通用习惯，比如“先搭骨架”和“模块化原则”。经过这段时间在大学里更系统地刷题和打比赛，我想专门来聊聊算法竞赛里绝对绕不开、也常常让初学者（包括曾经的我）痛不欲生的一座大山——动态规划（Dynamic Programming，简称 DP）。

在处理 DP 题的时候，我们经常会陷入一个死胡同：“我看懂了题意，但我就是不知道怎么定义状态，更写不出状态转移方程。” 看着题解里极其简洁的一句 dp[i][j] = max(...)，常常会有种“这到底是怎么想出来的”的挫败感。

但在刷了足够多的题之后，我发现 DP 其实并没有那么玄乎。它本质上就是一种 “带备忘录的聪明版暴力枚举”。而且，我们完全可以通过一些非常实用的小技巧，快速“猜”出状态的定义，并推导出转移的维度。以下是我总结出的两道“杀手锏”。

1. 见微知著：从“数据范围”反推状态维度 ​

很多新手的习惯是拿着题目空想：“这题到底是一维 DP 还是二维 DP？”其实，题目本身已经把最大的提示直接塞到你手里了，那就是变量的数据范围。

在绝大多数算法竞赛（如 Codeforces、牛客、蓝桥杯）中，时间和空间的限制是死板的。通常来说，现代评测机一秒钟大约能跑 $10^8$ 次运算，而常规的空间限制（比如 256MB）大概能存下几千万个 int 类型的整数。

我的实战法则是：把题目给的核心变量范围乘起来，只要总和在 $10^7$ 级别以内，那我们大概率可以直接把所有的变量都塞进 dp 数组的维度里！

化大为小与最优解的传递 ​

DP 最核心的思想就是化大为小。既然数据范围允许，我们只要开一个数组，把每一个“子状态”的最优解都记录下来。因为 DP 满足“无后效性”（简单来说就是：我不管你以前是怎么走到这一步的，我只在乎你现在的状态），所以我们只要确保当前状态记录的是最优解，那么把这个状态传递给下一个状态时，得出的最终解也必然是最优解。

💡 举个实在的例子：0-1 背包问题变体 ​

假设题目给了你 $N$ 个物品，每个物品有重量 $W$ 和体积 $V$，让你求在背包限重 $M$、限容 $K$ 的情况下的最大价值。 你看了一眼数据范围：

• 物品数量 $N \le 100$
• 背包限重 $M \le 100$
• 背包限容 $K \le 100$

这三个数字一出来，别犹豫，直接算乘积：$100 \times 100 \times 100 = 10^6$。这个数字远小于 $10^7$！ 这几乎就是在明示你：这题的状态定义就是一个三维数组 dp[i][j][k]！

• i 代表考虑前 i 个物品。
• j 代表当前使用的重量。
• k 代表当前使用的体积。

如果我们把数据范围改一下：$N \le 1000$，$M \le 1000$。乘起来是 $10^6$。那毫无疑问，状态定义就是二维的 dp[i][j]。

总结一下： 当你对状态定义毫无头绪时，去看数据范围！有几个约束条件的数据乘起来能在 $10^7$ 以内，就开几维数组，把这些约束条件全部作为状态的下标。这是打破思维僵局的最快方法。

2. 逆向思维：看全局，从“终点”往“起点”细分 ​

如果你用第一步的技巧确定了 dp 数组大概长什么样（比如确定了是 dp[i][j]），接下来的拦路虎就是状态转移方程了。

很多人的思维习惯是顺向的：试图从 dp[1][1] 开始，去想它能变成谁。这种“推”的思路在遇到复杂题目时往往会面临分支太多的问题，导致脑子一团乱麻。

我认为更有效的方法是看全局，逆向倒推。想一下，全局最优解是由前面哪些“仅差一步”的子状态得来的？ 然后不断细分，状态转移方程自然就浮出水面了。

💡 举个实在的例子：二维网格的最小路径和 ​

假设有一个 $N \times M$ 的网格，每个格子里有一定数量的金币 cost[i][j]。你只能向右或向下走，问从左上角 (1,1) 走到右下角 (N,M)，最少要花多少体力？

不要从 (1,1) 开始想！我们直接把目光放在终点 (N,M) 上。

1. 确定全局终点： 全局最优解就是我们站在终点的那一刻，即 dp[N][M]（代表走到 (N,M) 所需的最小体力）。
2. 寻找“前置状态”： 我要怎么才能踏进 (N,M) 这个格子？因为题目规定只能向右或向下走，所以我一定、且只能从它的“上方”格子 (N-1, M) 或者“左方”格子 (N, M-1) 走过来。
3. 写出转移方程： 既然只有这两条路，那我作为一个贪心的人，肯定选这两条路里体力花费比较小的那条，再加上当前格子本身的消耗。 于是，方程秒出： dp[n][m] = min(dp[n-1][m], dp[n][m-1]) + cost[n][m]

你看，一旦我们采取了“从大到小”、“从终点找前驱”的逆向拆解法，原本虚无缥缈的逻辑瞬间就变成了确定的数学公式。这个思想可以套用在绝大多数 DP 题目上。

比如经典的最长公共子序列（LCS）： 求字符串 $A$（长度为 $N$）和 $B$（长度为 $M$）的最长公共子序列。

• 全局目标： dp[N][M] 代表整个字符串匹配的结果。
• 找前置状态： 看最后两个字符 $A[N]$ 和 $B[M]$。
  • 如果它们相等，那好办，相当于捡了个大便宜，直接由它们各自去掉最后一个字符的状态转移过来：dp[N][M] = dp[N-1][M-1] + 1。
  • 如果它们不相等，说明 $A[N]$ 和 $B[M]$ 不可能同时存在于最长子序列中。那我要么舍弃 $A$ 的最后一个字符，要么舍弃 $B$ 的最后一个字符。于是就是：dp[N][M] = max(dp[N-1][M], dp[N][M-1])。

通过这样“剥洋葱”式的不断细分，不管多复杂的 DP 题，其实都能被拆解成两三个简单的选择题。

3. 一些额外的唠叨：警惕边界与初始化 ​

掌握了上面两点（看变量定维度、逆向推导找方程），其实你已经能稳稳拿下大部分基础和进阶的 DP 题了。但在我实际敲代码的血泪史中，还要补充一个极易踩坑的细节：初始化边界。

很多时候，你状态猜对了，方程也写对了，但样例就是跑不过。这往往是因为最初的起点（比如 dp[0][0]）没有初始化好。

我的经验是：

• 如果题目要求的是最大值（max），那么记得把 DP 数组一开始全刷成非常小的负数（比如 -1e18 或 -0x3f3f3f3f），防止一些非法的空状态干扰答案。
• 如果要求的是最小值（min），就刷成非常大的正数（比如 0x3f3f3f3f）。
• 然后，只把绝对合法的起跑线（比如最开始的 dp[0][0] 或 dp[1][1]）手动赋值为合法的初始值（通常是 0 或者是起点的实际数值）。

结语 ​

回顾一下，其实搞懂 DP 并没有捷径，但有套路。先盯紧变量数据范围这块“指路牌”，确立你的多维数组；然后再站在全局最优解的终点，像侦探一样去逆推是哪几个“嫌疑人（前置状态）”导致了这个结果。

大学时间确实充裕，这给了我们可以坐在屏幕前为一道 DP 题冥思苦想一个下午的资本。那些绞尽脑汁后，评测机终于弹出绿色 Accepted 的瞬间，可能就是算法竞技带给我们最纯粹的乐趣吧。