第一章引言——什么是多状态DP1.1 传统DP的局限在经典的线性DP中我们通常定义dp[i]表示“前 i 个元素的最优解”。但现实问题中一个“位置”或“时刻”往往对应着多种不同的处境。例如在股票交易中你当前要么持有股票要么未持有。在打家劫舍中你当前要么偷了这家要么没偷。在考试策略中你当前要么正常答题要么处于“冷静”状态要么处于“爆发”状态。如果只用一维状态dp[i]我们丢失了“当前处于什么状态”的关键信息。多状态DP应运而生。1.2 多状态模型的核心思想定义多个DP数组或者定义多维DP状态分别表示在同一个阶段位置/时间下不同“模式”下的最优值。状态机视角将问题建模为有限状态自动机Finite State Machine, FSM。每个阶段状态之间根据“动作”或“规则”进行转移。核心公式dp[i][state]最优值最大/最小/方案数dp[i][state]最优值最大/最小/方案数其中state枚举了当前时刻所有可能的情况。第二章基础模型——线性场景下的多状态2.1 模型一打家劫舍系列House Robber2.1.1 基础版不能偷相邻状态定义dp[i][0]偷到第 i 家且第 i 家没偷时的最大金额。dp[i][1]偷到第 i 家且第 i 家偷了时的最大金额。转移方程dp[i][0]max⁡(dp[i−1][0],dp[i−1][1])dp[i][0]max(dp[i−1][0],dp[i−1][1])dp[i][1]dp[i−1][0]nums[i]dp[i][1]dp[i−1][0]nums[i]初始化dp[0][0]0,dp[0][1]nums[0]dp[0][0]0,dp[0][1]nums[0]答案max⁡(dp[n−1][0],dp[n−1][1])max(dp[n−1][0],dp[n−1][1])代码Ccppint rob(vectorint nums) { int n nums.size(); if (n 0) return 0; vectorvectorint dp(n, vectorint(2, 0)); dp[0][1] nums[0]; for (int i 1; i n; i) { dp[i][0] max(dp[i-1][0], dp[i-1][1]); dp[i][1] dp[i-1][0] nums[i]; } return max(dp[n-1][0], dp[n-1][1]); }空间优化由于只依赖前一项可以压缩到O(1)。2.1.2 进阶版环形打家劫舍核心首尾不能同时偷。解法拆分成两个单排问题。偷第一间不偷最后一间范围[0, n-2]不偷第一间偷最后一间范围[1, n-1]取最大值。多状态思想虽然用了两次DP但每次DP内部依然是双状态模型。2.1.3 树形打家劫舍多状态的树形DP状态定义dp[u][0]不偷节点 u 时以 u 为根的子树的最大金额。dp[u][1]偷节点 u 时以 u 为根的子树的最大金额。转移dp[u][0]∑v∈children(u)max⁡(dp[v][0],dp[v][1])dp[u][0]v∈children(u)∑​max(dp[v][0],dp[v][1])dp[u][1]∑v∈children(u)dp[v][0]val[u]dp[u][1]v∈children(u)∑​dp[v][0]val[u]DFS 后序遍历实现。2.2 模型二股票交易系列Best Time to Buy and Sell Stock这是多状态DP的经典教学案例状态机思想体现得淋漓尽致。2.2.1 基础模型无限次交易含冷冻期/手续费状态定义经典三状态dp[i][0]第 i 天结束后不持有股票且不在冷冻期的最大利润。dp[i][1]第 i 天结束后持有股票的最大利润。dp[i][2]第 i 天结束后不持有股票且处于冷冻期的最大利润。状态机图文字描述状态0空仓非冷保持空仓非冷- 状态0买入股票- 状态1状态1持仓保持持仓- 状态1卖出股票- 状态2进入冷冻期状态2空仓冷冻冷冻期结束自动进入状态0转移方程dp[i][0]max⁡(dp[i−1][0],dp[i−1][2])dp[i][0]max(dp[i−1][0],dp[i−1][2])dp[i][1]max⁡(dp[i−1][1],dp[i−1][0]−prices[i])dp[i][1]max(dp[i−1][1],dp[i−1][0]−prices[i])dp[i][2]dp[i−1][1]prices[i]dp[i][2]dp[i−1][1]prices[i]初始化dp[0][0]0,dp[0][1]−prices[0],dp[0][2]0dp[0][0]0,dp[0][1]−prices[0],dp[0][2]0注意第0天不可能处于冷冻期但设为0不影响比较2.2.2 含手续费的版本状态定义双状态dp[i][0]第 i 天不持有股票的最大利润。dp[i][1]第 i 天持有股票的最大利润。转移dp[i][0]max⁡(dp[i−1][0],dp[i−1][1]prices[i]−fee)dp[i][0]max(dp[i−1][0],dp[i−1][1]prices[i]−fee)dp[i][1]max⁡(dp[i−1][1],dp[i−1][0]−prices[i])dp[i][1]max(dp[i−1][1],dp[i−1][0]−prices[i])注意手续费在卖出时扣除也可以在买入时扣除两种写法等效只需保证一致性。2.2.3 最多K笔交易状态定义dp[i][k][0/1]表示第 i 天最多进行 k 笔交易当前持有状态为 0 或 1 时的最大利润。转移dp[i][k][0]max⁡(dp[i−1][k][0],dp[i−1][k][1]prices[i])dp[i][k][0]max(dp[i−1][k][0],dp[i−1][k][1]prices[i])dp[i][k][1]max⁡(dp[i−1][k][1],dp[i−1][k−1][0]−prices[i])dp[i][k][1]max(dp[i−1][k][1],dp[i−1][k−1][0]−prices[i])复杂度O(n*k)当 k 很大时需要优化如 k n/2 时退化为无限次交易。2.2.4 交易次数与状态维度的关系1笔交易可以用一次遍历但多状态思想体现在buy1、sell1两个变量。2笔交易可以扩展为buy1, sell1, buy2, sell2四个变量本质上是在维护两个阶段的状态。第三章多状态DP的通用建模方法3.1 状态机的五步法识别阶段通常以“位置”、“时间”、“物品”作为阶段划分。枚举所有可能的状态在这个阶段下主体可能处于哪些“模式”。画出状态转移图箭头表示动作或条件标注转移代价。写出转移方程根据图用数学公式表达。确定初始化和边界第一阶段的各个状态如何赋值。3.2 典型的多状态分类类型示例状态数二状态打家劫舍、股票含手续费2三状态股票含冷冻期3多层状态最多K笔股票交易2*(K1)组合状态买/卖/休息 次数限制多维3.3 状态压缩与优化滚动数组当dp[i]只依赖dp[i-1]时用两个变量或两个长度为状态数的数组滚动。位运算状态压缩当状态数很少如 2^m时用整数表示状态集合。单调队列优化在含“冷却”或“延迟”的DP中有时需要维护窗口极值。第四章经典题型深度解析4.1 买卖股票的最佳时机含冷冻期LeetCode 309题目卖出后第二天为冷冻期不能买入。多状态解法已在上文给出。这里我们深入分析为什么必须用三状态而不是二状态。错误尝试只用两个状态hold和empty。问题empty无法区分是“刚卖完”还是“早已空仓”。如果无法区分则无法正确判断是否允许买入因为刚卖完的第二天不能买。三状态的必要性必须区分“冷冻期”这个特殊状态它虽然也是空仓但受限制。空间优化代码pythondef maxProfit(prices): n len(prices) if n 1: return 0 dp0, dp1, dp2 0, -prices[0], 0 # 非冷冻空仓持仓冷冻空仓 for i in range(1, n): new_dp0 max(dp0, dp2) new_dp1 max(dp1, dp0 - prices[i]) new_dp2 dp1 prices[i] dp0, dp1, dp2 new_dp0, new_dp1, new_dp2 return max(dp0, dp2)4.2 最佳买卖股票时机含手续费LeetCode 714二状态解法pythondef maxProfit(prices, fee): cash, hold 0, -prices[0] for p in prices[1:]: cash max(cash, hold p - fee) hold max(hold, cash - p) return cash解读cash相当于dp[i][0]hold相当于dp[i][1]。这里手续费在卖出时扣除。4.3 粉刷房子Paint House问题一排房子每个房子可以刷红、蓝、绿三种颜色相邻房子颜色不能相同成本矩阵costs[n][3]求最小总成本。状态定义dp[i][j]表示第 i 间房子刷成颜色 j 时的最小总成本。转移dp[i][j]min⁡k≠jdp[i−1][k]costs[i][j]dp[i][j]kjmin​dp[i−1][k]costs[i][j]复杂度O(n*3^2)可优化到O(n*3)通过记录最小值和次小值。多状态本质每个阶段有 3 个状态状态间转移受限制不能相邻同色。4.4 字符交替打印类似“摆动序列”问题给定一个序列求最长交替子序列上升、下降交替。每个位置可以处于“上升尾”或“下降尾”两种状态。状态up[i]以 i 结尾的最长摆动子序列长度且最后一步是上升。down[i]以 i 结尾的最长摆动子序列长度且最后一步是下降。转移up[i]max⁡(up[i−1],down[i−1]1)if nums[i]nums[i−1]up[i]max(up[i−1],down[i−1]1)if nums[i]nums[i−1]down[i]max⁡(down[i−1],up[i−1]1)if nums[i]nums[i−1]down[i]max(down[i−1],up[i−1]1)if nums[i]nums[i−1]第五章复杂场景——多维度状态5.1 多维状态的定义当问题的约束条件不止一个时我们需要增加维度。示例K 次交易 冷冻期状态dp[day][k][status]其中 status 可以是 0/1持仓/空仓或者引入冷冻期后变成 0/1/2。示例背包 物品状态每个物品有“未选”、“选一次”、“选多次”等状态对应有限背包或完全背包的不同转移。5.2 路径中的多状态问题机器人从左上角到右下角每个格子有障碍求路径数但允许最多使用一次“穿越”技能无视障碍。状态扩展dp[i][j][0]到达 (i,j) 且未使用技能时的路径数。dp[i][j][1]到达 (i,j) 且已使用技能时的路径数。转移从上方或左方来如果当前格子是障碍未使用技能则不能进入除非起点特殊处理。已使用技能则可通过但技能已在之前使用。这种建模方式将“技能使用次数”作为一维状态非常典型。5.3 多状态 计数DP问题给定数字序列求有多少种子序列满足某种条件如不包含相邻相同数字。状态dp[i][j]表示考虑前 i 个位置最后选择的数字是 j 的方案数。转移时需要遍历所有可能的上一数字复杂度可能达到O(n * 种类^2)此时可以用前缀和优化。第六章优化技巧与复杂度分析6.1 空间优化滚动数组当dp[i]只与dp[i-1]相关时将第一维压缩为 2。原地更新如果状态之间转移不相互覆盖可以用一维数组但需要小心更新顺序通常倒序更新。6.2 时间优化单调队列在“有限交易次数”的股票问题中如果 k 很大可以用单调队列将O(n*k)优化到O(n log k)甚至O(n)。矩阵快速幂如果状态转移是线性的且阶段数极大如 10^18可以用矩阵快速幂。例如求递推数列的第 n 项每个阶段状态数 ≤ 10 时可用。6.3 状态化简对称性如果多个状态本质等价可以合并。依赖关系有时可以用差值代替绝对值减少状态维度。示例股票问题中如果只有一次交易可以化简为min_price和max_profit两个变量本质上是将“状态”隐含在遍历过程中。第七章实战代码模板Python版7.1 通用多状态DP框架线性pythondef solve_multistate_dp(n, states, transition_func): # states: 状态数量 # dp[i][s]: 前 i 个阶段处于状态 s 的最优值 dp [[-inf] * states for _ in range(n)] # 初始化第0阶段 for s in range(states): dp[0][s] init_value(0, s) for i in range(1, n): for s in range(states): # 根据转移函数从上一阶段的所有状态转移到当前状态 dp[i][s] transition_func(dp[i-1], i, s) return max(dp[n-1])7.2 股票含冷冻期完整版pythondef maxProfit(prices): n len(prices) if n 1: return 0 dp0, dp1, dp2 0, -prices[0], 0 for i in range(1, n): new_dp0 max(dp0, dp2) new_dp1 max(dp1, dp0 - prices[i]) new_dp2 dp1 prices[i] dp0, dp1, dp2 new_dp0, new_dp1, new_dp2 return max(dp0, dp2)7.3 粉刷房子空间优化pythondef minCost(costs): if not costs: return 0 n len(costs) dp costs[0][:] # 初始化第一间房子的三种颜色成本 for i in range(1, n): new_dp [0, 0, 0] new_dp[0] costs[i][0] min(dp[1], dp[2]) new_dp[1] costs[i][1] min(dp[0], dp[2]) new_dp[2] costs[i][2] min(dp[0], dp[1]) dp new_dp return min(dp)第八章易错点与调试技巧8.1 常见错误状态定义不清晰混淆了“阶段”和“状态”。阶段通常是位置或时间状态是模式。转移遗漏状态机图中没有穷举所有可能的边。初始化错误例如在股票问题中第0天持有股票的利润应为-prices[0]而不是0。边界处理数组越界或状态在边界处无定义。8.2 调试方法打印DP表在小规模样例上手动验证转移是否正确。状态机验证画出状态转移图确保每个状态都有入边和出边除非是终止状态。对拍与暴力枚举对比当 n 很小时。第九章总结与扩展9.1 多状态DP的本质多状态DP是将“阶段”和“模式”解耦通过状态机描述问题中的约束条件。它比单纯的一维DP更具表现力能够解决大量带有“状态依赖”的优化问题。9.2 与其他DP类型的结合区间DP 多状态如“括号匹配”中除了左右边界还有当前栈的状态。树形DP 多状态如“树上最大独立集”每个节点有选/不选两种状态。数位DP 多状态如“不含前导零且相邻数字差≥2”的数状态包括“是否处于前导零”、“上一个数字是什么”、“是否已触及上限”。9.3 学习建议从简单二状态开始理解“偷”与“不偷”、“持有”与“空仓”的逻辑。掌握状态机画法这是设计复杂DP的利器。刷透股票系列它是多状态DP的集大成者。尝试自己设计状态遇到新题先问“在某个位置有哪些可能的处境”附录经典习题列表题目难度状态数要点LeetCode 198. 打家劫舍中等2基础二状态LeetCode 213. 打家劫舍 II中等2环形环形处理LeetCode 337. 打家劫舍 III中等2树形DPLeetCode 121. 买卖股票的最佳时机简单隐式状态可转为单变量LeetCode 122. 买卖股票的最佳时机 II中等2无限次交易LeetCode 123. 买卖股票的最佳时机 III困难4两次交易LeetCode 188. 买卖股票的最佳时机 IV困难2*(K1)K次交易LeetCode 309. 最佳买卖股票时机含冷冻期中等3三状态机LeetCode 714. 买卖股票的最佳时机含手续费中等2手续费处理LeetCode 256. 粉刷房子中等3相邻不同色LeetCode 265. 粉刷房子 II困难KK种颜色优化LeetCode 376. 摆动序列中等2上升/下降尾