3573. 买卖股票的最佳时机 V
考点
- 状态机DP
- 滚动数组
- 初始值设置
易错点
在状态设计上，不应以单次操作的正负来抉择，比如你设定0代表不变，1代表正，2代表负
1 | 正 |
可以看见，出现了正0正这种诡异的路线，而我们题目要求的一定是类似正..负或负..正的转移路径
所以我们必须按照“交易状态”这个整体进行设计
除此之外，交易次数一共是K次，那么买入卖出的交易次数一共就是2K次，按照2K进行定义时，初始化会方便很多
因为没有任何操作下的最大值和买/卖了0次下的最大值的初始化难度完全不一样
答案也不一定是操作了2K次就是最大的，可能你多买卖反而亏本了，所以要遍历所有的f[1~2K][n][0]
思路
1. 状态设计：用“操作次数”而不是“交易次数”
题目中，一笔完整交易可以是：
- 正向：买入 → 卖出
- 反向（做空）：卖出 → 买回
并且：
- 任意一天最多进行一次操作（买 / 卖）
- 同一时刻最多只持有一笔仓位（空仓 / 多头 / 空头）
- 最多允许进行 \(K\) 笔完整交易
一笔完整交易包含两次操作：开仓一次、平仓一次。 因此可以把“操作次数”作为 DP 的计数轴：最多允许 \(2K\) 次操作。
设数组： \[ f[k][i][s] \] 含义：
- \(i \in [0,n]\)：考虑完前 \(i\) 天（对应
prices[0..i-1]） - \(k \in [0,2K]\)：到目前为止，总共进行了 \(k\) 次操作（买或卖）
- \(s \in \{0,1,2\}\)：当前仓位状态
- \(s = 0\)：空仓（没有持多也没有持空）
- \(s = 1\)：持有多头（之前有一次买入但尚未卖出）
- \(s = 2\)：持有空头（之前有一次卖出但尚未买回）
则 \[ f[k][i][s] = \text{在考虑前 } i \text{ 天、总共进行了 } k \text{ 次操作且当前状态为 } s \text{ 时的最大利润。} \]
2. 初始值设定
代码中：
1 | memset(f, 0xcf, sizeof(f)); |
解释如下。
2.1 非法状态全部置为负无穷
通过
1 | memset(f, 0xcf, sizeof(f)); |
将整个数组填成一个很小的负数（例如 \(-10^{15}\) 量级），记为 \(-\infty\)。这表示：
- 默认所有状态一开始都是“不可能到达”的非法状态。
这样做的好处是：
- 后续做
max转移时，只有真正有路径到达过的状态才能参与竞争； - 避免从未初始化的“垃圾状态”中“捡到”无意义的利润。
数学上，相当于： \[ f[k][i][s] = -\infty \quad \text{(初始默认)} \]
2.2 唯一合法起点：0 次操作 + 任意天数 + 空仓
接着设定：
1 | for (int i = 0; i <= n; ++i) |
含义是：在没有任何操作的情况下，始终保持空仓，利润为 0。 注意这里对所有 \(i\) 都赋值，是因为：
- “第 0 天之前什么也不做”是合法的；
- “前 1 天什么也不做”也合法；
- …
- 一直到“前 n 天什么也不做”都可以视为“0 次操作 + 空仓 = 0 利润”。
因此，合法初始状态为： \[ \forall i \in [0,n]:\quad f[0][i][0] = 0,\quad f[0][i][1] = f[0][i][2] = -\infty. \]
3. 状态转移推导
以第 \(i\) 天价格 \(p = prices[i-1]\) 为例。
外层循环：
1 | for (int k = 1; k <= K << 1; ++k) { |
表示按“操作次数 k”层层推进，在每一层上把所有天数 i
的状态更新完。
下面分三种状态说明转移方程。
3.1 转移到空仓状态 \(f[k][i][0]\)
代码：
1 | f[k][i][0] = max( |
数学形式： \[ f[k][i][0] = \max \Bigl( f[k-1][i-1][1] + p,\; f[k-1][i-1][2] - p,\; f[k][i-1][0] \Bigr). \] 含义：
从多头平仓到空仓：
- 昨天（第 \(i-1\) 天）是多头，进行了 \(k-1\) 次操作，状态为 \(f[k-1][i-1][1]\)；
- 今天第 \(k\) 次操作：卖出多头，价格为 \(p\)，增加收益 \(+p\)；
- 升级为 \(k\) 次操作，变成空仓。 因此这一支贡献为：
\[ f[k-1][i-1][1] + p. \]
从空头平仓到空仓：
- 昨天是空头，进行了 \(k-1\) 次操作，状态为 \(f[k-1][i-1][2]\)；
- 今天第 \(k\) 次操作：买回空头，付出价格 \(p\)，收益变化 \(-p\)；
- 升级为 \(k\) 次操作，变成空仓。 对应项为：
\[ f[k-1][i-1][2] - p. \]
保持空仓不动：
- 昨天已经是空仓，进行了 \(k\) 次操作，今天不做任何事；
- 状态从 \(f[k][i-1][0]\) 延续到 \(f[k][i][0]\)，利润不变。
因此三种情况取最大。
3.2 转移到多头状态 \(f[k][i][1]\)
代码：
1 | f[k][i][1] = |
数学形式： \[ f[k][i][1] = \max \Bigl( f[k][i-1][1],\; f[k-1][i-1][0] - p \Bigr). \] 含义：
- 继续持有多头：
- 昨天已经是多头，进行了 \(k\) 次操作；
- 今天不做操作，保持多头，状态从 \(f[k][i-1][1]\) 直接延续。
- 从空仓开多：
- 昨天空仓，进行了 \(k-1\) 次操作，状态 \(f[k-1][i-1][0]\)；
- 今天第 \(k\) 次操作：买入一股，多头开仓，支付价格 \(p\)，利润变化 \(-p\)；
- 于是变成 \(f[k][i][1] = f[k-1][i-1][0] - p\)。
3.3 转移到空头状态 \(f[k][i][2]\)
代码：
1 | f[k][i][2] = |
数学形式： \[ f[k][i][2] = \max \Bigl( f[k][i-1][2],\; f[k-1][i-1][0] + p \Bigr). \] 含义与多头类似，只是方向相反：
- 继续持有空头：
- 昨天已经是空头，进行了 \(k\) 次操作；
- 今天不做任何事，空头仓位保持。
- 从空仓开空（先卖后买）：
- 昨天空仓，进行了 \(k-1\) 次操作；
- 今天第 \(k\) 次操作：先卖出一股，开空头，立刻获得 \(+p\) 的现金流；
- 因此变成 \(f[k][i][2] = f[k-1][i-1][0] + p\)。
4. 最终答案的选择
代码部分：
1 | long long res = neg; |
表示： \[ \text{ans} = \max_{1 \le k \le 2K} f[k][n][0]. \] 理由如下：
- 最终必须空仓 只有在空仓状态下，所有交易都已经闭合（开仓与平仓成对出现），利润是“真正在手上的钱”。 因此只考虑 \(f[k][n][0]\)。
- 不强制用满 \(K\) 笔交易 使用的交易次数越多不一定越好（有时多一次交易反而亏钱）， 但允许最多 \(K\) 笔交易，对应“最多 \(2K\) 次操作”。 因此只需要在 \(k \in [1, 2K]\) 范围内取最大值即可。 若某些 \(k\) 对应的状态无法到达，就一直保持为 \(-\infty\)，不会影响答案。
5. 代码
这份代码很可能超时，因为数组开太大了：
1 | class Solution { |
所以滚动数组一下即可：
1 | class Solution { |