如何思考一个动态规划问题需要几个状态？

第一步：思考 角色

问自己：我当前的状态可能有哪些不同的“角色”？

• 比如买卖股票问题：

  • 有可能是持股、卖出、休息，→ 3 种角色

• 背包问题：

  • 角色比较固定：容量 / 物品选择

状态数 ≈ 当前时刻下，决策行为或状态的枚举情况

第二步：考虑 过去的影响

问自己：我做一个动作，会不会受到前一天某种特定状态的限制？

• 如果有“冷冻期”，说明不是所有状态之间都能直接转移 → 你就需要引入“冷冻”这个额外状态

• 如果只有买卖无限制，两个状态就够（持股 / 不持股）

状态数 ≈ 为了准确区分不同限制路径，你需要多少“分支状态”来表示

第三步：画出状态转移图

手动画出：

• 节点 = 状态

• 边 = 状态转移（由什么转到什么）

如果画出状态图后，发现某个状态没有前驱或不影响结果，那说明可能是冗余状态，可以删去

第四步：写出状态转移方程

通过写递推公式，你会发现：

• 如果公式里无法统一表达当前动作，可能因为状态粒度不够细

• 如果写着写着发现状态分不清，可能因为状态定义太模糊，需要拆分更多状态

第五步：验证是否能覆盖所有路径 + 边界

确认：

• 所有可能的行为（买、卖、等）都能用已有状态表示

• 边界条件（第一天、最后一天）状态是否有明确初始化

几个常见题目

题目 / 问题类型	状态数	状态解释
买卖股票（无限次，无限制）	2	持股 / 不持股
买卖股票（含冷冻期）	3	持股 / 卖出 / 冷冻
买卖股票（最多两次）	4	第一次买 / 第一次卖 / 第二次买 / 第二次卖
0-1 背包问题	1 或 2	一维表示容量，或二维加物品维度
打家劫舍（不能偷连续两家）	2	偷/不偷

总结：

“状态由角色定，变化看限制，画出状态图看转移是否清晰，冗余是否可合并。”