188. 买卖股票的最佳时机 IV
如何推导状态转移方程？
当前层的每一个状态来自上一层的哪些状态？
若状态转移方程中出现复杂计算，改变dp数组的定义或增加dp数组的维度。
class Solution {public int maxProfit(int k, int[] prices) {if (prices.length == 0) return 0;int n = prices.length;// dp[i][j][0/1]:// i：第 i 天（0-based）// j：已完成的交易次数（最多 j 次买卖）// 0：不持股；1：持股int[][][] dp = new int[n][k + 1][2];// 初始化：第 0 天// 不持股自然收益为 0；持股意味着在第 0 天买入，收益为 -prices[0]for (int j = 0; j <= k; j++) {dp[0][j][0] = 0; // 第 0 天不持股dp[0][j][1] = -prices[0]; // 第 0 天持股（买入）}// 状态转移从第 1 天开始for (int i = 1; i < n; i++) {for (int j = 1; j <= k; j++) {// dp[i][j][0] —— 第 i 天不持股的最大利润// 两种方式：// 1) 昨天不持股，今天不操作// 2) 昨天持股，今天卖出（卖出后交易数仍为 j）dp[i][j][0] = Math.max(dp[i - 1][j][0],dp[i - 1][j][1] + prices[i]);// dp[i][j][1] —— 第 i 天持股的最大利润// 两种方式：// 1) 昨天持股，今天不操作// 2) 昨天不持股，今天买入（买入开始第 j 次交易）dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]);}}// 最终结果：最后一天、不持股、完成最多 k 次交易的最大收益return dp[n - 1][k][0];}
}下面将以严格的动态规划推导方式解释本题中三维 DP 的递推公式为何这样写，并从状态含义、动作选择、转移推导三个角度给出完整推导。
一、状态定义为什么是 dp[i][j][0/1]
我们定义：
-
i：第 i 天（0 ≤ i < n）
-
j：到目前为止最多进行了 j 次“完整交易”（一次交易 = 买 + 卖）
-
0/1：当前是否持有股票
0→ 不持有1→ 持有
因此：
dp[i][j][0] = 第 i 天、最多完成 j 次交易时、不持股的最大利润
dp[i][j][1] = 第 i 天、最多完成 j 次交易时、持股的最大利润
二、每个状态能来自哪些前一天的状态？
我们按“今天是否持股”分类讨论。
1）推导 dp[i][j][0] —— 今天不持股
今天不持股，有两种可能：
情况 A：昨天也不持股，今天什么也不做
dp[i-1][j][0]
情况 B：昨天持股，今天卖出（完成一次交易）
如果今天卖出，则交易数不增加（因为“买”已经算了交易的开始，“卖”完成交易，也算当前这一次仍属于 j 次交易内）。
换言之：我们仍然处于 “j 次交易” 的范围内。
昨天持股 → 今天卖出：
dp[i-1][j][1] + prices[i]
所以两者取最大值：
dp[i][j][0] = max( dp[i-1][j][0], dp[i-1][j][1] + prices[i] )
2）推导 dp[i][j][1] —— 今天持股
今天持股，也有两种可能：
情况 A：昨天就持股，今天不操作
dp[i-1][j][1]
情况 B：昨天不持股，今天买入
买入会开始一次交易，因此交易次数应从 j-1 过渡到 j：
昨天不持股且已经完成了 j-1 次交易 → 今天买入
dp[i-1][j-1][0] - prices[i]
因此：
dp[i][j][1] = max( dp[i-1][j][1], dp[i-1][j-1][0] - prices[i] )
三、为什么买入时交易次数 j 要减一？
这是很多同学的疑惑。
在股票问题中，“一次交易”通常指 买 + 卖。
我们采用的定义是：
交易次数 j 表示“卖出操作的次数”，即已有多少次完整交易。
因此：
- 买入不会立即增加交易次数
- 卖出会完成一次交易（但在这个 DP 定义下，卖出仍然处于 j 次交易的状态，不需要 +1）
而买入要从“上一次完整交易次数 j-1” 来，因为：
买入只能发生在卖出后，因此必须从 j-1 的不持有状态转移
这就是：
dp[i][j][1] = dp[i-1][j-1][0] - prices[i]
的数学理由。
四、初始化为何是 dp[0][i][1] = -prices[0]
在第 0 天，如果我们持股票，则表示第 0 天买入：
dp[0][j][1] = -prices[0]
这里 j 任意（1 ≤ j ≤ k）都可以买入，但最多只是为了统一化处理，不影响最终答案。
五、全公式总结（和你代码一致）
不持有状态：
dp[i][j][0] = \max( dp[i-1][j][0],\ dp[i-1][j][1] + prices[i] )
持有状态：
dp[i][j][1] = \max( dp[i-1][j][1],\ dp[i-1][j-1][0] - prices[i] )
六、直观解释（非数学推导，帮助理解）
- 卖出状态 = （昨天就不持股）vs（今天卖掉）
- 持股状态 = （昨天就持股）vs（今天买入）
图示：
昨天持股 ----卖出→ 今天不持股↑ ↑└------买入←------┘
七、你真正应该记住的核心逻辑
- dp[i][j][0] 由 “昨天不持股” 或 “昨天持股并今天卖出” 来
- dp[i][j][1] 由 “昨天持股” 或 “昨天不持股并今天买入” 来
- 买入动作对应从 j-1 次交易转移到 j 次交易