第一步：思考 角色

問自己：我當前的狀態可能有哪些不同的“角色”？

• 比如買賣股票問題：

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

• 背包問題：

  • 角色比較固定：容量 / 物品選擇

狀態數 ≈ 當前時刻下，決策行為或狀態的枚舉情況

第二步：考慮 過去的影響

問自己：我做一個動作，會不會受到前一天某種特定狀態的限制？

• 如果有“冷凍期”，說明不是所有狀態之間都能直接轉移 → 你就需要引入“冷凍”這個額外狀態

• 如果只有買賣無限制，兩個狀態就夠（持股 / 不持股）

狀態數 ≈ 為了準確區分不同限制路徑，你需要多少“分支狀態”來表示

第三步：畫出狀態轉移圖

手動畫出：

• 節點 = 狀態

• 邊 = 狀態轉移（由什么轉到什么）

如果畫出狀態圖后，發現某個狀態沒有前驅或不影響結果，那說明可能是冗余狀態，可以刪去

第四步：寫出狀態轉移方程

通過寫遞推公式，你會發現：

• 如果公式里無法統一表達當前動作，可能因為狀態粒度不夠細

• 如果寫著寫著發現狀態分不清，可能因為狀態定義太模糊，需要拆分更多狀態

第五步：驗證是否能覆蓋所有路徑 + 邊界

確認：

• 所有可能的行為（買、賣、等）都能用已有狀態表示

• 邊界條件（第一天、最后一天）狀態是否有明確初始化

幾個常見題目

題目 / 問題類型	狀態數	狀態解釋
買賣股票（無限次，無限制）	2	持股 / 不持股
買賣股票（含冷凍期）	3	持股 / 賣出 / 冷凍
買賣股票（最多兩次）	4	第一次買 / 第一次賣 / 第二次買 / 第二次賣
0-1 背包問題	1 或 2	一維表示容量，或二維加物品維度
打家劫舍（不能偷連續兩家）	2	偷/不偷

總結：

“狀態由角色定，變化看限制，畫出狀態圖看轉移是否清晰，冗余是否可合并。”