LeetCode 188. Best Time to Buy and Sell Stock IV

题意 + 思路一句话概括：这是「最多进行 k 次交易」的股票买卖问题，可以用三维 DP：dp[day][transaction][hold]dp[day][transaction][hold]dp[day][transaction][hold]，其中交易数按「卖出次数」计数，买入不加 1，卖出才加 1。leetcode

题目与难点

给定整数 k 和数组 prices，prices[i] 表示第 i 天的股价，要求在至多 k 笔交易内获得最大利润。leetcode
一次交易 = 一次买入 + 一次卖出，不能同时持有多笔仓位（必须卖了才能再买）。leetcode
这题的难点在于：
既要限制交易次数，又要正确处理「持股/不持股」状态。
朴素暴力会爆炸，需要用状态机 DP 来精确刻画每天的选择。

状态设计与含义

采用三维 DP：
dp[i][j]dp[i][j]dp[i][j]：第 iii 天结束，已经完成了 jjj 次交易，且当前不持股的最大利润。
dp[i][j][2]dp[i][j][2]dp[i][j][2]：第 iii 天结束，已经完成了 jjj 次交易，且当前持股的最大利润。
关键约定：
j 表示的是「完成的交易数 = 完成的卖出次数」。
买入：不改变 j。
卖出：使 j 从 j−1j-1j−1 变成 jjj。
这样定义带来的好处：
交易次数的增加只发生在卖出动作上，语义清晰。
约束「至多 k 次交易」就变成了 0 <= j <= k。

初始化细节

设：
day_count = pricesSize。
transaction_count = k + 1（因为交易数 j 取值范围是 0…k，一共 k+1 种）。leetcode
hold_count = 2（0 表示不持股，1 表示持股）。
初始化三维数组 dp[day_count][transaction_count][2]，全部置为一个很小的值 INF_MIN，表示「不可能的状态」。leetcode
第 0 天：
不持股：
dp=0dp = 0dp=0：第 0 天结束，不持股，且尚未完成任何交易，利润为 0。
对于 j>0j > 0j>0，dp[0][j][0] = INF_MIN：第 0 天不可能完成任何卖出，所以这些都是非法状态。
持股：
dp[2]=−pricesdp[2] = -pricesdp[2]=−prices：如果第 0 天结束时选择持股，那么唯一方式就是第 0 天买入一次，利润为 −prices-prices−prices。
对于 j>0j > 0j>0，dp[0][j][1] = INF_MIN：第 0 天不可能既持股又已经完成卖出。
注意：
状态存在，并不代表一定会选；最终答案是从所有可能状态取最大值。

状态转移方程

在第 i 天（i >= 1），枚举所有交易数 j（0…k）：

不持股状态

dp[i][j]={dp[i−1],j=0max⁡(dp[i−1][j], dp[i−1][j−1][2]+prices[i]),j>0dp[i][j] = \begin{cases} dp[i-1], & j = 0 \ \max\big(dp[i-1][j],\ dp[i-1][j-1][2] + prices[i]\big), & j > 0 \end{cases}dp[i][j]={dp[i−1],max(dp[i−1][j], dp[i−1][j−1][2]+prices[i]),j=0j>0
直观解释：
j == 0：
还没有完成任何交易，所以今天不可能「卖出」；只能继承「昨天也不持股」。
j > 0：
要么昨天就不持股并且已经完成了 j 次交易，今天什么都不做；
要么昨天持股并完成了 j-1 次交易，今天卖出获得 prices[i]，完成第 j 次交易。
这正体现了「卖出时交易数 +1」的逻辑。

持股状态

dp[i][j][2]=max⁡(dp[i−1][j][2], dp[i−1][j]−prices[i])dp[i][j][2] = \max\big(dp[i-1][j][2],\ dp[i-1][j] - prices[i]\big)dp[i][j][2]=max(dp[i−1][j][2], dp[i−1][j]−prices[i])
解释：
昨天已经持股且完成了 j 次交易，今天什么都不做；
昨天不持股并完成了 j 次交易，今天买入一股，交易数不变，但现金少了 prices[i]。
注意这里的关键点：
买入不改变 j。
不能从 dp[i-1][j][1] - prices[i] 来转移，否则变成「在已经持股的基础上再买一次」，违反「不能同时持有多份股票」的约束。

最终答案与遍历顺序

当所有天数都算完后：
最后一天必须是不持股状态才能保证利润已经完全兑现。
遍历所有 0 <= j <= k：
ans=max⁡0≤j≤kdp[day_count−1][j]\text{ans} = \max_{0 \le j \le k} dp[day_count-1][j]ans=0≤j≤kmaxdp[day_count−1][j]
遍历顺序建议：
外层：天数 i 从 1 到 day_count - 1。
中层：交易数 j 从 0 到 k。
边界处理：
当 j == 0 时，计算 dp[i][0][0] 不能访问 dp[i-1][-1][1]，所以单独特判。
其余情况按状态转移方程即可。

时间复杂度与空间优化

在当前三维 DP 实现中：
状态数量：day_count * (k+1) * 2，时间复杂度 O(nk)O(nk)O(nk)。
空间复杂度同样为 O(nk)O(nk)O(nk)，因为 day、transaction、hold 都作为维度存在。
优化方向：
滚动数组：
转移中 dp[i] 只依赖 dp[i-1]，可以把 day 这一维压掉，用 dp[transaction_count][2] 来存当前天，整体空间降为 O(k)O(k)O(k)。
大 k 特判：
若 k >= pricesSize / 2，则限制形同虚设，可以视为「不限次数交易」问题，直接用贪心：只要 prices[i] > prices[i-1] 就把差额加入利润。leetcode

对应 C 实现要点（与你的代码对齐）

你的代码核心部分与上述思路一致，关键点包括：leetcode
三维 dp 的 malloc 与初始化：
外三层分别对应 day_count、transaction_count 和 hold_count。
每个元素先填充为 INF_MIN，代表不可能状态。
第 0 天初始化：
dp[0][0][NOT_HOLD] = 0;
dp[0][0][HOLD] = -prices[0];

转移：
不持股：
j==0：只能 dp[i][0][NOT_HOLD] = dp[i-1][0][NOT_HOLD];
j>0：

dp[i][j][NOT_HOLD]=MAX(dp[i-1][j][NOT_HOLD],dp[i-1][j-1][HOLD]+price);

持股：

dp[i][j][HOLD]=MAX(dp[i-1][j][HOLD],dp[i-1][j][NOT_HOLD]-price);

最终答案：

max_profit=INF_MIN;for(j=0;j<transaction_count;j++)max_profit=MAX(max_profit,dp[day_count-1][j][NOT_HOLD]);

结束后释放所有 malloc 的内存，避免内存泄漏。leetcode

面试官视角下的典型追问

在面试场景中，如果你给出上述定义和转移，面试官很可能继续问你：
为什么交易次数用「卖出次数」来计，而不是买入次数？
如果要你把三维 DP 优化成二维 / 一维，如何改写代码？状态遍历顺序会有什么要求？
当 k 特别大（例如 k >= n/2）时，有没有必要继续用 O(nk)O(nk)O(nk) 的 DP？贪心解法是怎样的？leetcode
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/description/?envType=study-plan-v2&envId=top-interview-150
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/submissions/1875439908/?envType=study-plan-v2&envId=top-interview-150