各位同学好，我是你们的信奥辅导老师。

每年带学生备考CSP-J复赛，我都会说一句话： "得动态规划者得复赛。"

但很多同学学DP的方式完全错了——背了一堆模型模板，上了考场还是不会。为什么？因为DP的难点从来不是"代码怎么写"，而是 "拿到一道题，怎么想到用DP？怎么定义状态？怎么推出转移方程？"

今天这篇文章，我不讲模型罗列，不讲模板背诵。我只讲一件事：拿到一道DP题，完整的思考过程是什么样的。 从读题到拆解，从状态定义到转移推导，一步一步带你走一遍。

一、DP的核心：大问题拆成小问题

很多同学觉得DP很玄，其实它的核心思想特别朴素：

❝

一个大问题的答案，可以由比它小一圈的问题的答案推出来。

什么是"最优子结构"？

举个最简单的例子：走楼梯，每次走1阶或2阶，要计算走到第10阶的最少步数。最优方案中，最后一步要么是从第9阶走1步上来，要么是从第8阶走2步上来。无论哪种情况，前面走到第9阶（或第8阶）的部分一定也是最优的——如果走到第9阶有更省步数的走法，那整体走到第10阶的步数也会更少。

这就是最优子结构：大问题的最优解，包含了小问题的最优解。

什么是"无后效性"？

还是走楼梯的例子：你现在站在第5阶，接下来怎么走只取决于你现在在第几阶，不取决于你之前是怎么走到第5阶的——不管你是5步都走1阶上来的，还是先走2阶再走1阶上来的，只要现在站在第5阶，后面的最优选择就完全一样。

这就是无后效性：一旦确定了当前状态，之前的决策不会影响后面的最优选择。

❝

老师提醒：判断一道题能不能用DP，就问自己两个问题：①大问题能不能拆成更小的同类问题？②确定了当前状态后，之前的路径还会不会影响后面？第一个是"是"、第二个是"不会"，就可以用DP。

二、状态怎么定义？——从"最后一步"倒推

这是DP最关键的一步，也是90%的同学卡住的地方。

核心技巧：盯住"最后一步"

拿到一道题，不要从头开始想，而是盯住最后一步。问自己：

❝

"要得到最终答案，最后一步我做了什么决策？"

这个决策，就是连接"大问题"和"小问题"的桥梁。

例子1：走楼梯

题目：n阶楼梯，每次走1阶或2阶，有多少种走法？

盯住最后一步：要走到第n阶，最后一步是怎么走的？

• 可能是从第n-1阶走1步上来的
• 可能是从第n-2阶走2步上来的

只有这两种可能！那走到第n阶的走法数，就等于"走到n-1阶的走法数"加上"走到n-2阶的走法数"。

于是状态自然就定义出来了：

• dp[i] = 走到第i阶的走法数
• 转移：dp[i] = dp[i-1] + dp[i-2]

你看，不是凭空想出dp[i]的，是从"最后一步有几种可能"倒推出来的。

例子2：数字三角形

题目：从三角形顶部走到底部，每步只能走到下一行相邻位置，求最大路径和。

盯住最后一步：要走到最后一行的某个位置，最后一步是从哪来的？

• 从右上方来
• 从左上方来

只有这两种可能！那到当前位置的最大路径和，就等于"上方两个位置的最大路径和"加上当前数字。

状态定义：

• dp[i][j] = 从顶部走到第i行第j列的最大路径和
• 转移：dp[i][j] = a[i][j] + max(dp[i-1][j], dp[i-1][j-1])

状态定义的三个原则

1. 状态要能描述"走到哪了" ：比如走楼梯的"第i阶"、数字三角形的"第i行第j列"
2. 状态要能由更小的状态推出来：如果定义了一个状态，发现它没法由前面的状态算出来，那定义就错了
3. 状态的维度尽量少：能用一维就不用二维，能用二维就不用三维（CSP-J一般不超过二维）

❝

老师提醒：定义状态时，把dp[i]或dp[i][j]的含义用一句话写在注释里，越具体越好。比如不要写"dp[i]表示前i个的答案"，要写"dp[i]表示走到第i阶楼梯的走法总数"。含义清楚了，转移方程自然就出来了。

三、转移方程怎么推？——枚举"最后一步的所有可能"

状态定义好了，转移方程其实就是一句话：

❝

当前状态的值 = 所有可能的前驱状态，按题目要求取max/min/求和。

三种常见的转移类型

例子3：01背包

题目：n件物品，每件体积w[i]、价值v[i]，只能选一次，容量m的背包最多装多少价值？

盯住最后一步：考虑第n件物品，最后对它做了什么决策？

• 不选它：那问题就变成"前n-1件物品，容量m"的最大价值
• 选它（前提是装得下）：那问题就变成"前n-1件物品，容量m-w[n]"的最大价值，再加上v[n]

只有这两种可能！取较大的那个。

状态定义：

• dp[i][j] = 前i件物品，容量j时的最大价值
• 转移：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])

例子4：最长上升子序列（LIS）

题目：求序列中最长的严格上升子序列长度。

盯住最后一步：考虑以第i个数结尾的最长上升子序列，最后一步加的是哪个数？

• 第i个数前面，可以接任何一个比它小的数a[j]（j < i）
• 所有可能的j都枚举一遍，取最大的

状态定义：

• dp[i] = 以第i个数结尾的最长上升子序列长度
• 转移：dp[i] = max(dp[j] + 1)，其中j < i且a[j] < a[i]

推导转移的检查清单

写完转移方程后，问自己三个问题：

1. 有没有漏掉某种可能？ 比如01背包，除了"选"和"不选"，还有第三种可能吗？没有。
2. 前驱状态是不是都已经算过了？ 比如dp[i]用到dp[i-1]，那i必须从小到大遍历。
3. 边界条件处理了吗？ 比如数字三角形第一列没有左上方，LIS前面没有更小的数时dp[i]=1。

四、初始化：DP的起点

转移方程告诉你"怎么从前面算后面"，但最开始的状态从哪来？这就是初始化。

初始化的思路

**找"最小的子问题"**——小到不能再拆了，答案是显然的，那就是初始化的值。

❝

老师提醒：初始化最容易出错。常见错误：求最大值时忘记初始化为负无穷，求方案数时忘记dp[0]=1（空方案也是一种方案）。写代码前先想清楚"最小的情况答案是什么"。

五、实战演练：一道真题的完整思考过程

光说不练假把式。我们用CSP-J 2025年T3 异或和这道真题，完整走一遍从读题到写出DP的全过程。

第1步：读题，明确问什么

题目大意：给定长度为n的非负整数序列a[1..n]，和一个非负整数k。你需要选出尽可能多的不相交区间，使得每个区间的异或和都等于k。求最多能选出多少个区间。

数据范围：n ≤ 500000，0 ≤ a[i] < 2²⁰，0 ≤ k < 2²⁰。

问的是"最多多少个"，所以转移时应该取max。

第2步：找性质——前缀异或

异或有一个和"前缀和"非常像的性质：

定义前缀异或 s[i] = a[1] ^ a[2] ^ ... ^ a[i]（s[0] = 0）。

那么区间[l, r]的异或和为：

a[l] ^ a[l+1] ^ ... ^ a[r] = s[r] ^ s[l-1]

❝

为什么？因为异或满足x ^ x = 0，s[r] ^ s[l-1] = (a[1]^...^a[r]) ^ (a[1]^...^a[l-1]) = a[l]^...^a[r]，前面的都抵消了。

所以"区间[l, r]的异或和等于k"等价于：

s[r] ^ s[l-1] = k，即 s[l-1] = s[r] ^ k

这个转化非常关键：把"找一个异或和为k的区间"变成了"找一个前缀异或值等于s[r]^k的位置"。

第3步：盯住最后一步，定义状态

盯住最后一步：考虑第i个数（也就是序列的最后一个数），它在不在我们选的区间里？

情况1：第i个数不在任何选中的区间里那前i个数的最优解，就等于前i-1个数的最优解：dp[i] = dp[i-1]

情况2：第i个数是某个选中区间的结尾假设这个区间是[l, i]，它的异或和为k。根据前缀异或的性质：

• s[i] ^ s[l-1] = k，即 s[l-1] = s[i] ^ k
• 选了这个区间后，前面只能用前l-1个数的最优解，再加上这1个区间
• 所以：dp[i] = dp[l-1] + 1

我们需要在所有满足s[l-1] = s[i] ^ k的l中，取dp[l-1]最大的那个。

状态定义：

• dp[i] = 前i个数中，最多能选出多少个不相交区间，每个区间异或和为k

第4步：推导转移——如何高效找前驱

转移方程很清楚：

dp[i] = max(dp[i-1], max{ dp[l-1] + 1 })

其中l满足s[l-1] = s[i] ^ k。

但如果每次都从头枚举所有l，时间复杂度是O(n²)，n=500000会超时。

优化技巧：注意到dp数组是单调不减的（多一个数，答案不可能变少）。所以对于同一个前缀异或值v，最后一次出现的位置对应的dp值最大。

我们维护一个数组pos[v]，表示前缀异或值为v的最后出现位置。那么：

• 需要找的前缀异或值是 s[i] ^ k
• 对应的最后位置是 pos[s[i] ^ k]
• 如果这个位置存在（≥0），就可以从它转移：dp[pos[s[i]^k]] + 1

最终转移方程：

如果 pos[s[i] ^ k] 存在：    dp[i] = max(dp[i-1], dp[pos[s[i] ^ k]] + 1)否则：    dp[i] = dp[i-1]

每次处理完i后，更新pos[s[i]] = i（记录这个前缀异或值的最新位置）。

第5步：初始化

• dp[0] = 0（0个数，选不出区间）
• pos[0] = 0（前缀异或值0出现在位置0）
• 其他pos值初始化为-1（表示还没出现过）

第6步：组装答案

答案就是dp[n]——前n个数的最优解。

最终代码

#include<bits/stdc++.h>usingnamespacestd;constint MAXV = 1 << 20;  // 异或值的范围 [0, 2^20)int dp[500005];     // dp[i] = 前i个数最多选多少个区间int pos[MAXV];      // pos[v] = 前缀异或值为v的最后位置，-1表示未出现intmain(){int n, k;cin >> n >> k;memset(pos, -1, sizeof(pos));    pos[0] = 0;      // 前缀异或值0出现在位置0    dp[0] = 0;int s = 0;       // 当前前缀异或和for (int i = 1; i <= n; i++) {int x;cin >> x;        s ^= x;      // 更新前缀异或和int target = s ^ k;  // 需要找的前缀异或值if (pos[target] != -1) {// 可以选一个以i结尾的区间[pos[target]+1, i]            dp[i] = max(dp[i-1], dp[pos[target]] + 1);        } else {// 找不到这样的区间，不选以i结尾的            dp[i] = dp[i-1];        }        pos[s] = i;  // 更新前缀异或值s的最后位置    }cout << dp[n] << endl;return0;}

❝

老师点评：这道题的DP本身非常基础——就是经典的"选/不选"两种决策，一维状态，转移也很简单。真正的考点有两个：

1. 前缀异或转化：把"区间异或和为k"转化为"两个前缀异或值的关系"，这是异或类题目的标准套路
2. 高效查找前驱：利用dp单调不减的性质，用pos数组记录每个前缀异或值的最后出现位置，把O(n²)降到O(n)

这道题完美体现了DP的思考流程：盯住最后一步（第i个数是不是区间结尾）→ 枚举两种可能（选/不选）→ 定义状态→ 推导转移→ 发现朴素转移太慢→ 用数据结构优化。CSP-J复赛的DP题往往都是这样：模型是经典的，但需要你结合题目性质做一步转化或优化。

六、拿到一道DP题的思考流程

把前面的内容浓缩成一张流程图，考场按这个顺序想：

读题，明确问什么（max/min/计数？）    ↓看数据范围，有没有什么提示？    ↓找性质，能不能转化成经典问题？（前缀和？排序？）    ↓盯住"最后一步"：最后做了什么决策？    ↓枚举最后一步的所有可能（选/不选？从哪来？）    ↓定义状态：dp[...] = 什么什么的答案（有几个约束就几维）    ↓写转移：当前 = 所有前驱按要求取max/min/求和    ↓找最小子问题，写初始化    ↓转移会不会超时？能不能用数据结构优化？    ↓确定答案在哪（dp[n]？max(dp)？直接取？）    ↓写代码，打印dp表调试

七、常见坑与调试技巧

坑1：状态定义太模糊

dp[i]到底代表什么？写代码前用一句话写在注释里。定义模糊，转移必错。

坑2：漏掉某种转移可能

比如LIS，是不是所有j < i且a[j] < a[i]的情况都枚举了？数字三角形，边界位置（第一列、最后一列）的转移是不是特殊处理了？

坑3：初始化错误

• 求最大值：初始化为0还是负无穷？如果答案可能是负数，必须用负无穷！
• 求方案数：dp[0] = 1了吗？空方案也是一种方案！
• 求最小值：初始化为正无穷了吗？

坑4：遍历顺序错误

• 01背包一维版：j从大到小（防止重复使用）
• 完全背包一维版：j从小到大（允许重复使用）
• 有依赖的转移：确保前驱状态已经算过

坑5：转移超时不优化

很多DP题的朴素转移是O(n²)，但n=1e5或5e5时会超时。这时候要想：

• 能不能用前缀和/后缀和优化？
• 能不能用单调队列/堆维护最优前驱？
• 能不能用哈希/数组记录关键信息（比如这道题的pos数组）？

数据范围是最好的提示：n=500000就在告诉你必须O(n)或O(n log n)。

坑6：忽略dp的单调性

很多DP数组是单调不减的（比如这道题），这意味着"最后出现的位置往往最优"。利用单调性可以大幅简化优化。

调试神器：打印dp表

如果结果不对，不要盯着代码看，把整个dp数组打印出来，手动算前几个小例子对比。哪一行开始和预期不一样，错误就在那一步的转移里。

写在最后

动态规划不是靠"背模型"学会的，是靠"想清楚"学会的。

拿到一道题，不要急着套模板，先问自己：

1. 最后一步做了什么决策？
2. 这个决策对应哪些更小的子问题？
3. 状态怎么定义才能描述这些子问题？有几个约束？
4. 转移是取max、min还是求和？
5. 最小的情况答案是什么？
6. 数据范围给了我什么提示？需要优化吗？

把这六个问题想清楚，代码自然就出来了。模型只是"见过的题型"，思考方法才是"以不变应万变"的能力。

建议大家找5道历年DP真题，不看题解，强制自己按这个流程想一遍。哪怕花一小时想一道题，也比半小时抄一道题解收获大。

如果这篇文章对你有帮助，欢迎点赞、在看、转发给一起备考的同学。有任何问题，欢迎在评论区留言，老师会逐一解答。