状态机 DP 将问题建模为有限状态之间的转移，每个阶段根据当前状态做出决策并转移到下一状态。它是解决"带约束选择"问题（如股票买卖系列）的通用框架。
一、核心思想
Mermaid · 渲染中（下方为源码）
graph LR A[状态机DP] --> B[阶段分离] B --> C[状态转移边] C --> D[决策最小化/最大化]
将 DP 的"阶段"和"状态"显式分离：
- 阶段：时间/位置（第 i 天、第 i 个字符）
- 状态：当前所处的模式（持有/不持有、奇数次/偶数次）
转移 = 在当前状态下做决策 → 进入下一状态。
二、股票买卖系列
一次交易（LeetCode 121）
状态：0=不持有，1=持有
int maxProfit(int[] prices) {
int hold = -prices[0], cash = 0;
for (int i = 1; i < prices.length; i++) {
cash = Math.max(cash, hold + prices[i]); // 卖出
hold = Math.max(hold, -prices[i]); // 买入
}
return cash;
}无限次交易（LeetCode 122）
int maxProfit(int[] prices) {
int hold = -prices[0], cash = 0;
for (int i = 1; i < prices.length; i++) {
int newCash = Math.max(cash, hold + prices[i]);
int newHold = Math.max(hold, cash - prices[i]);
cash = newCash;
hold = newHold;
}
return cash;
}