动态规划：简单多状态模型 —— 从入门到状态机设计

第一章：引言——什么是多状态DP？

1.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 Robber）

2.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])

代码（C++）：

cpp

int rob(vector<int>& nums) { int n = nums.size(); if (n == 0) return 0; vector<vector<int>> dp(n, vector<int>(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 进阶版：环形打家劫舍

核心：首尾不能同时偷。
解法：拆分成两个单排问题。

1. 偷第一间，不偷最后一间：范围[0, n-2]

2. 不偷第一间，偷最后一间：范围[1, n-1]

3. 取最大值。

多状态思想：虽然用了两次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 状态机的五步法

1. 识别阶段：通常以“位置”、“时间”、“物品”作为阶段划分。

2. 枚举所有可能的状态：在这个阶段下，主体可能处于哪些“模式”。

3. 画出状态转移图：箭头表示动作或条件，标注转移代价。

4. 写出转移方程：根据图，用数学公式表达。

5. 确定初始化和边界：第一阶段的各个状态如何赋值。

3.2 典型的多状态分类

3.3 状态压缩与优化

• 滚动数组：当dp[i]只依赖dp[i-1]时，用两个变量或两个长度为状态数的数组滚动。

• 位运算状态压缩：当状态数很少（如 2^m）时，用整数表示状态集合。

• 单调队列优化：在含“冷却”或“延迟”的DP中，有时需要维护窗口极值。

第四章：经典题型深度解析

4.1 买卖股票的最佳时机含冷冻期（LeetCode 309）

题目：卖出后第二天为冷冻期，不能买入。

多状态解法（已在上文给出）。这里我们深入分析为什么必须用三状态，而不是二状态。

错误尝试：只用两个状态hold和empty。

• 问题：empty无法区分是“刚卖完”还是“早已空仓”。如果无法区分，则无法正确判断是否允许买入（因为刚卖完的第二天不能买）。

三状态的必要性：必须区分“冷冻期”这个特殊状态，它虽然也是空仓，但受限制。

空间优化代码：

python

def 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）

二状态解法：

python

def 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框架（线性）

python

def 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 股票含冷冻期（完整版）

python

def 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 粉刷房子（空间优化）

python

def 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 常见错误

1. 状态定义不清晰：混淆了“阶段”和“状态”。阶段通常是位置或时间，状态是模式。

2. 转移遗漏：状态机图中没有穷举所有可能的边。

3. 初始化错误：例如在股票问题中，第0天持有股票的利润应为-prices[0]，而不是0。

4. 边界处理：数组越界或状态在边界处无定义。

8.2 调试方法

• 打印DP表：在小规模样例上手动验证转移是否正确。

• 状态机验证：画出状态转移图，确保每个状态都有入边和出边（除非是终止状态）。

• 对拍：与暴力枚举对比（当 n 很小时）。

第九章：总结与扩展

9.1 多状态DP的本质

多状态DP是将“阶段”和“模式”解耦，通过状态机描述问题中的约束条件。它比单纯的一维DP更具表现力，能够解决大量带有“状态依赖”的优化问题。

9.2 与其他DP类型的结合

• 区间DP + 多状态：如“括号匹配”中，除了左右边界，还有当前栈的状态。

• 树形DP + 多状态：如“树上最大独立集”，每个节点有选/不选两种状态。

• 数位DP + 多状态：如“不含前导零且相邻数字差≥2”的数，状态包括“是否处于前导零”、“上一个数字是什么”、“是否已触及上限”。

9.3 学习建议

1. 从简单二状态开始，理解“偷”与“不偷”、“持有”与“空仓”的逻辑。

2. 掌握状态机画法，这是设计复杂DP的利器。

3. 刷透股票系列，它是多状态DP的集大成者。

4. 尝试自己设计状态：遇到新题，先问“在某个位置，有哪些可能的处境？”

附录：经典习题列表