状态机 DP：股票买卖问题

一、面试常考点

1. 状态机思维

把“持有/不持有”等状态拆开建模。

2. 高频变体

最多交易一次、多次、含冷冻期、含手续费。

二、细节介绍

1. 基础状态

hold：当天结束持有股票的最大收益。 cash：当天结束不持有股票的最大收益。

2. 转移

hold = max(hold, cash - price) cash = max(cash, hold + price)（注意临时变量顺序）

三、示例代码

function maxProfit(prices) {
  let hold = -Infinity
  let cash = 0

  for (const p of prices) {
    const prevHold = hold
    hold = Math.max(hold, cash - p)
    cash = Math.max(cash, prevHold + p)
  }

  return cash
}

四、常用应用场景

1. 有状态最优决策

如库存、仓位、任务状态切换优化。

2. 规则变体多的题

状态机建模可扩展性高。