动态规划状态机模型：从KMP到股票买卖的通用解题框架

1. 项目概述从线性DP到状态机思维的跃迁在算法竞赛和面试准备中动态规划DP一直是区分选手水平的核心分水岭。很多朋友在掌握了基础的线性DP、背包问题后遇到一些更复杂的序列处理问题比如“不能连续选择”、“带有前后依赖关系的选择”时常常会感到思路卡壳状态转移方程怎么写都觉得别扭。AcWing 1052这道题以及它所代表的“状态机模型”正是打通这个关节的关键钥匙。我自己在刷题和带新手的过程中无数次看到学习者在这里完成一次重要的思维升级——从简单地定义f[i]表示前i个元素的某种属性到主动设计一个“机器”用f[i][j]来精确描述“处理到第i位时机器处于j状态”下的最优解。简单来说状态机模型就是把DP过程中的每个“阶段”通常是序列的下标i再细分成若干个互斥的“状态”。这些状态代表了在当前阶段我们所关心的对象所处的具体“情形”。转移也不再是简单的从i-1到i而是从一个(i-1, 状态A)转移到(i, 状态B)这个转移过程必须遵循我们预先定义好的“状态转移规则”就像一台精密的自动机运行一样。这种方法特别适合处理带有“限制条件”的序列问题比如不能选相邻元素、股票买卖的冷冻期、字符串匹配中的KMP状态跳转等。掌握了它你会发现很多看似棘手的DP问题 suddenly变得清晰且有章可循。2. 状态机模型的核心思想与抽象方法2.1 为什么需要状态机线性DP的局限性我们先回想一下最经典的线性DP问题比如“打家劫舍”问题不能偷窃相邻的房屋。最直接的思路是定义f[i]为偷窃前i个房屋能获得的最大金额。状态转移时对于第i个房屋我们有两种选择偷或不偷。如果偷那么f[i] f[i-2] nums[i]如果不偷那么f[i] f[i-1]。取两者最大值。这个思路没问题但它隐含了一个信息f[i-1]这个状态它本身可能对应着第i-1个房屋被偷或没被偷两种子情况。当我们计算f[i]选择“不偷”时我们其实并不关心f[i-1]是怎么来的直接用它即可。但如果我们遇到更复杂的限制呢比如“你最多只能连续休息两天”、“卖出股票后有一天冷冻期不能买入”。这时仅仅用f[i]一个维度就无法准确描述“当前处于什么情况”了因为“是否处于冷冻期”、“已经连续休息了几天”这些信息是做出下一步决策的关键依据但它们没有被记录在状态里。状态机模型就是为了解决这个问题而生的。它的核心是将每个阶段下标i的可能情况显式地定义为若干个明确的状态。然后我们不再计算一个笼统的f[i]而是计算f[i][state]表示“处理完前i个元素后处于state状态下的最优解”。状态之间的转移必须遵循现实规则形成一个有向图。这样一来所有限制条件都被编码在了状态定义和转移规则中思路会异常清晰。2.2 构建状态机的四步法从我个人的经验来看构建一个状态机DP模型可以遵循以下四个步骤我把它称为“状态机四步拆解法”第一步识别阶段与状态核心变量阶段通常是序列的索引i时间、步骤。状态则是为了做出当前决策必须知道的、关于“当前时刻情形”的关键信息。这个信息往往是一个有限的、离散的集合。例如在股票问题中状态可能是“持有股票”或“未持有股票”在“不能连续选择”问题中状态可能是“最后一个元素被选了”或“最后一个元素没选”。第二步精确定义每个状态的含义这是最关键的一步必须用一句无歧义的话说明f[i][j]到底代表什么。例如f[i][0]: 考虑前i个字符且第i个字符不参与构成特定模式串时的最大价值。f[i][1]: 考虑前i个字符且第i个字符参与构成特定模式串时的最大价值。 定义不清后续转移一定会混乱。第三步绘制状态转移图不要只在脑子里想一定要画出来。用圆圈表示状态用有向边表示可能的转移边上标明转移的条件和收益或代价。这张图是你整个DP的逻辑蓝图。它让你一眼看清所有可能的路径避免遗漏。对于AcWing 1052这类与字符串匹配结合的问题状态转移图会和KMP算法的next数组紧密耦合。第四步根据转移图写出状态转移方程将图翻译成数学语言。对于每个状态f[i][j]遍历所有能转移到它的前驱状态f[i-1][k]加上转移的代价或收益取最优值。初始化通常是f[0][某个初始状态] 0其他为负无穷求最大值时或正无穷求最小值时表示不可达。注意状态机模型和“状态压缩DP”状压DP是两回事。状态机关注的是单个对象在不同“模式”间的切换状态数量很少且固定状压DP通常是用一个整数的二进制位来表示多个独立物体的选取情况状态数量是指数级的。别把这两个“状”字搞混了。3. AcWing 1052设计密码——状态机与KMP的完美融合3.1 问题重述与难点解析AcWing 1052 “设计密码”是一道经典题它完美体现了状态机模型的应用价值。题目大意是你需要设计一个长度为N的密码字符串S只包含小写字母。同时给定一个模式串T长度不超过50 也仅含小写字母。要求密码S中不能包含子串T。求满足条件的密码S的总数。最暴力的想法是生成所有长度为N的字符串26^N个逐个检查是否包含子串T。这显然是不可行的。一个常见的优化思路是DPf[i]表示设计了前i位密码且不包含子串T的方案数。但问题来了如何保证“不包含子串T”当我们决定第i1位填什么字母时我们需要知道前i位密码的“后缀”与模式串T的匹配情况因为新加的字母可能会和前面的后缀拼接形成一个新的、更长的与T的前缀匹配的串甚至直接匹配出完整的T。这正是KMP算法解决的问题。KMP中的next数组记录了当匹配失败时模式串指针应该回退到的位置。我们可以把KMP匹配过程本身看作一个状态机状态就是当前模式串T的匹配指针位置j0 j M。j的含义是当前密码串的后缀已经成功匹配了模式串T的前j个字符。那么f[i][j]的状态定义就可以出来了表示已经设计了密码的前i位且当前密码串的后缀与模式串T匹配的长度为j即KMP匹配指针位于j的所有方案数。这里j必须小于M模式串长度因为一旦j等于M就意味着匹配到了完整的T这是非法状态其方案数应为0。3.2 状态转移的详细推导假设模式串T的长度为M。我们有一个KMP的next数组通常next[0] -1但为了方便我们使用从0开始的next数组并处理next[0]0。现在我们要从f[i][j]转移到f[i1][k]。我们处于状态(i, j)意味着前i位密码的后缀匹配了T的前j位。现在我们要为第i1位选择一个字母c。这个c会导致匹配指针j如何变化呢这正是KMP算法的核心过程如果c等于T[j]那么匹配长度自然增加1即新状态k j 1。如果c不等于T[j]那么我们需要根据next数组回退匹配指针直到找到一个位置p使得T[p]等于c或者回退到0。这个过程是p j; while (p 0 T[p] ! c) p next[p];。如果最终T[p] c则k p 1否则k 0。但是在DP转移时我们不能对每个f[i][j]和每个字母c都去跑一遍while循环那样复杂度太高。我们可以进行预处理对于每个状态j0 j M和每个可能的字母c‘a’到’z’我们预先计算出当处于状态j并遇到字符c时下一个状态k会是多少。我们把这个预处理的转移函数记为trans[j][c]。如何计算trans[j][c]这本质上是一个“自动机”的构建过程在AC自动机里叫建立trie图在这里就是KMP状态机的扩展。如果T[j] c那么trans[j][c] j 1。如果T[j] ! c那么我们就需要回退。注意这里回退到的位置不是简单的next[j]而是要检查T[next[j]]是否等于c不等于则继续回退。我们可以用类似DP的方式计算设x next[j]然后检查T[x]与c如果相等trans[j][c] x 1否则x再变成next[x]继续检查……这个过程可以递推计算或者直接写一个循环。更高效的方法是利用已经算好的trans[next[j]][c]因为next[j]比j小所以当我们计算trans[j][c]时trans[next[j]][c]已经计算好了。如果T[j] ! c那么trans[j][c] trans[next[j]][c]。有了trans数组状态转移方程就非常清晰了 对于所有合法的f[i][j]j M枚举第i1位的字母c‘a’到’z’计算k trans[j][c]。如果k M说明这个字母c会导致我们匹配到完整的T这是非法的所以这个转移不产生方案。如果k M那么这个转移是合法的我们有f[i1][k] f[i][j]。初始化f[0][0] 1。表示还没开始设计密码0位匹配长度为0的方案数为1空串。其他f[0][j]都为0。 最终答案ans sum(f[N][j])其中j从0到M-1。因为长度为N的密码设计完成后只要匹配长度j没达到M就是合法的。3.3 代码实现与关键细节#include iostream #include cstring using namespace std; const int N 55, MOD 1e9 7; int n, m; char str[N]; // 模式串T int f[N][N]; // f[i][j] 表示前i位密码匹配长度为j的方案数 int trans[N][26]; // 转移函数 trans[j][c] - k int ne[N]; // KMP的next数组 int main() { cin n (str 1); m strlen(str 1); // 1. 构建KMP next数组 for (int i 2, j 0; i m; i) { while (j str[i] ! str[j 1]) j ne[j]; if (str[i] str[j 1]) j; ne[i] j; } // 2. 预处理状态转移矩阵 trans // trans[j][c] 表示当前匹配长度是j遇到字符c(ac)后新的匹配长度 for (int j 0; j m; j) { // 当前匹配长度j for (int c 0; c 26; c) { // 枚举下一个字符 int k j; // 从j开始尝试匹配 // 如果当前字符不匹配且k不是初始状态就回退 while (k str[k 1] ! a c) k ne[k]; // 出来之后要么k0要么str[k1]匹配 if (str[k 1] a c) k; // 如果k之后等于m了说明构成了完整模式串这是非法转移 // 在DP时我们遇到km就不转移所以这里可以记录k但DP时会判断 trans[j][c] k; } } // 3. DP过程 f[0][0] 1; // 初始状态 for (int i 0; i n; i) { // 已经设计了i位密码 for (int j 0; j m; j) { // 当前匹配长度是j for (int c 0; c 26; c) { // 枚举第i1位的字符 int k trans[j][c]; // 转移后的新匹配长度 if (k m) { // 只有新长度小于m才是合法转移 f[i 1][k] (f[i 1][k] f[i][j]) % MOD; } // 如果km则忽略不进行转移 } } } // 4. 统计答案 int res 0; for (int j 0; j m; j) res (res f[n][j]) % MOD; cout res endl; return 0; }关键细节与实操心得next数组与j的对应关系代码中str数组从1开始存储ne[i]表示当str[i]匹配失败时下一个应该尝试匹配的str的位置。在状态表示时我们的状态j匹配长度对应的是已经成功匹配了str[1...j]。所以当j状态下遇到字符c我们比较的是str[j1]和c。这个1的下标偏移很容易出错务必在纸上画清楚。非法状态的处理在预处理trans数组时即使计算出的k等于m我们也把它存下来。但在DP转移时我们只进行k m的转移。这意味着所有会导向完整匹配的路径在DP过程中被主动截断了。这是解决“不包含子串”问题的精髓。复杂度分析预处理trans数组的复杂度是O(26 * M^2)如果使用while循环回退或O(26 * M)如果使用递推优化。DP过程的复杂度是O(26 * N * M)。由于M最大为50N最大为50根据题目这个复杂度是完全可接受的。空间优化观察DP方程f[i1][...]只依赖于f[i][...]因此可以使用滚动数组将空间复杂度从O(N*M)优化到O(M)。这对于N较大的情况是必要的优化技巧。4. 状态机模型的经典变体与扩展应用掌握了AcWing 1052这道题你就掌握了状态机DP结合字符串匹配的核心。但这个模型的应用远不止于此。下面我分享几个常见的变体帮助你举一反三。4.1 股票买卖系列问题带冷冻期这是状态机模型最经典的入门应用题。以“最佳买卖股票时机含冷冻期”为例LeetCode 309。题目要求你可以进行多次交易但卖出股票后无法在第二天买入股票冷冻期1天。状态设计我们可以定义三个状态f[i][0]: 第i天结束后持有股票时的最大利润。f[i][1]: 第i天结束后不持有股票且处于冷冻期即今天卖出了股票时的最大利润。f[i][2]: 第i天结束后不持有股票且不处于冷冻期时的最大利润。状态转移f[i][0]今天持有股票可能昨天就持有今天继续持有或者昨天不持有且不处于冷冻期今天买入。f[i][0] max(f[i-1][0], f[i-1][2] - prices[i])f[i][1]今天卖出了股票只可能来自昨天持有股票今天卖出。f[i][1] f[i-1][0] prices[i]f[i][2]今天空闲可买入可能昨天就空闲或者昨天是冷冻期今天解冻。f[i][2] max(f[i-1][2], f[i-1][1])初始化f[0][0] -prices[0]第一天买入f[0][1] 0第一天不可能卖出f[0][2] 0。 答案max(f[n-1][1], f[n-1][2])最后一天持有股票肯定不是最优的。这个状态机清晰地刻画了“持有”、“卖出冷冻”、“空闲”三个状态间的转换关系所有限制条件冷冻期都体现在了转移规则里从状态1只能转移到状态2不能直接转移到状态0。4.2 打家劫舍系列问题树形状态机“打家劫舍 III”LeetCode 337是在二叉树上的打家劫舍。状态机思想在这里同样适用但状态是定义在每个树节点上的。状态设计对于以u为根的子树dp[u][0]: 不偷窃节点u的情况下以u为根的子树能偷窃到的最大金额。dp[u][1]: 偷窃节点u的情况下以u为根的子树能偷窃到的最大金额。状态转移后序遍历如果偷u(dp[u][1])那么左右子节点l,r都不能偷。dp[u][1] val[u] dp[l][0] dp[r][0]如果不偷u(dp[u][0])那么左右子节点可偷可不偷取最大值。dp[u][0] max(dp[l][0], dp[l][1]) max(dp[r][0], dp[r][1])这本质上也是一个状态机每个节点有两种状态选/不选其状态值依赖于子节点的状态并且父子节点状态间存在约束选了父亲就不能选儿子。通过这个简单的两状态模型我们成功将树形DP问题结构化。4.3 扩展结合AC自动机的多模式串匹配AcWing 1052是单模式串匹配。如果题目升级为“密码中不能出现给定字典中的任何一个模式串”这就是一个多模式串匹配问题需要用到AC自动机。AC自动机可以看作是KMP在多模式串上的扩展它本身就是一个状态机Trie图。每个节点代表一个“匹配状态”即当前已匹配到的所有模式串的前缀。构建好AC自动机后DP的状态定义就变成了f[i][j]表示设计了前i位密码且当前位于AC自动机节点j状态上的方案数。转移时从节点j出发枚举下一个字符c走到tr[j][c]Trie图中的转移。如果tr[j][c]节点或其fail链上的节点有模式串结尾标记那么这个转移就是非法的因为构成了某个模式串。其他部分与单模式串的DP完全类似。这种“DP 自动机”的套路在字符串计数、包含/不包含某些模式串的方案数问题中非常强大。5. 常见错误与调试技巧实录在实际编码和教学过程中我见过太多同学在状态机DP上踩坑。这里我把它们总结出来并给出调试思路。错误1状态定义模糊或冗余这是最根本的错误。状态必须精确定义且彼此互斥。比如在股票问题中如果把状态定义为“持有”和“不持有”就漏掉了“冷冻期”这个关键信息导致无法正确处理“卖出后隔一天才能买”的约束。调试方法在纸上画出你定义的状态并尝试用题目中的每个操作如买入、卖出、等待去驱动状态变化看是否能覆盖所有情况且不产生歧义。错误2转移方程遗漏或错误特别是当状态较多时容易漏掉某些转移边。或者在计算f[i][新状态]时错误地从f[i][旧状态]转移而不是从f[i-1][旧状态]转移。调试方法打印DP表对于小规模样例N3,4手动模拟并打印出整个f数组。对照你手算的结果看哪里对不上。画转移图验证对于每个f[i][j]根据你的代码反向追踪它是从哪些f[i-1][k]转移过来的权重是多少。检查这个追踪路径是否符合你手绘的状态转移图。错误3初始化错误状态机DP的初始化需要小心。通常只有合法的起始状态如f[0][0]被初始化为基准值0或1其他状态应初始化为“不可能”的值求最大初始化为负无穷求最小初始化为正无穷求方案数初始化为0。如果初始化错了结果会从第一步开始就歪掉。调试方法单独检查i0或i1时的DP表值看是否符合你对初始情况的理解。错误4下标与边界处理在AcWing 1052中j的范围是[0, M)k trans[j][c]可能等于M。如果数组开小了或者访问f[i][k]时没判断kM的情况就会导致数组越界或逻辑错误。调试方法使用assert语句或printf调试在关键步骤如计算trans、进行DP转移后打印出下标值确保它们在合法范围内。错误5模运算处理不当这类计数问题通常要求对一个大数取模。常见的错误有加法/乘法后忘记取模。减法后可能得到负数未处理成非负数(a - b MOD) % MOD。初始化-INF时如果用0x3f3f3f3f在做加法后可能溢出最好用-1e9这类值或者使用long long并仔细处理。调试方法用小的、容易手算的样例测试确保结果正确。对于大样例可以尝试对中间结果取一个不同的模数比如1e99来交叉验证或者用暴力程序对小数据打表对比。一个实用的调试技巧构造极端小数据当你的程序出错时不要只看题目给的样例。自己构造N1, M1N2, M1N1, M2这样的极端小数据。手动计算出所有合法密码然后与你的DP程序输出对比。往往能在这些最简单的情况下发现初始化或转移的逻辑漏洞。状态机DP的思维难度在于建模一旦模型建对代码其实是比较模板化的。多画图多定义清晰的状态从简单的例子开始验证是掌握这门技术的不二法门。