LC188. 买卖股票的最佳时机 IV

题目描述

给定一个数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

题目解析

题目在说什么

这道题是买卖股票系列里比较难的一题。简单说，你有一张股票价格表，比如 [3,2,6,5,0,3]，每天价格不同。你可以进行最多 k 次买卖（一次买入+一次卖出算一笔交易），每次必须先卖出才能再买入，目标是算出最多能赚多少钱。

举个例子：k=2，价格是 [3,2,6,5,0,3]，最优策略是：第2天（价格2）买入，第3天（价格6）卖出，赚4元；第5天（价格0）买入，第6天（价格3）卖出，赚3元。总共7元。注意不能在同一天又买又卖，也不能同时持有多个股票。

思路是怎么来的

想象你是一个股票交易员，每天收盘后都要做记录。你有一个小本子，每天记两件事：今天收盘时手里有没有股票？以及到目前为止最多还能交易几次？你希望记下每种情况下最多赚了多少钱。

这个问题的核心是“状态”。每一天，你的状态由两个因素决定： 1. 手里有没有股票（0表示没有，1表示有） 2. 最多还能交易几次（注意是“最多”，不是“已经交易了几次”）

为什么用“最多还能交易几次”？因为这样方便递推。比如今天你最多还能交易3次，那么昨天你可能也是最多还能交易3次（今天没操作），或者昨天最多还能交易2次（今天买入了一次，所以剩余次数减少）。

我们用一个三维数组 dp[i][k][b] 来记录这些状态：

• i 表示第几天（从0开始）
• k 表示最多还能交易几次（注意：这里k是剩余次数，不是已用次数）
• b 表示是否持有股票（0不持有，1持有）

数组的值就是在这种状态下能获得的最大利润。

这个思路其实是从“穷举”优化来的。如果不考虑效率，你可以枚举所有可能的买卖组合，但那样太慢。动态规划就是通过记录中间状态，避免重复计算。

代码逐步拆解

我们一步步看代码是怎么实现这个思路的。

1. 边界处理

if (prices == null || prices.length == 0) {
    return 0;
}

如果价格数组为空或长度为0，没有交易机会，利润为0。

2. 初始化三维数组

int length = prices.length;
int[][][] dp = new int[length][k + 1][2];

• length 是天数
• k+1 是因为交易次数可以从0到k，共k+1种可能
• 2 表示持有或不持有股票

3. 第0天的初始化

for (int j = 1; j <= k; j++) {
    dp[0][j][0] = 0;
    dp[0][j][1] = -prices[0];
}

第0天（第一天）：

• 如果不持有股票，利润是0（没买没卖）
• 如果持有股票，说明在第0天买入了，花了 prices[0] 元，所以利润是 -prices[0]（负的，因为钱花出去了）

注意这里 j 从1开始，因为 j=0 表示最多还能交易0次，这种情况在第0天不可能持有股票（因为买了就不能卖，而交易次数为0意味着不能卖），所以 dp[0][0][1] 没有意义，我们保持默认值0。

4. 动态规划核心循环

for (int i = 1; i < length; i++) {
    for (int j = 1; j <= k; j++) {
        // 今天不持有股票
        dp[i][j][0] = Math.max(dp[i-1][j][0], dp[i-1][j][1] + prices[i]);
        // 今天持有股票
        dp[i][j][1] = Math.max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i]);
    }
}

这段是核心，我们一行一行解释。

第一行：今天不持有股票 有两种可能：

• 昨天就不持有，今天没操作：dp[i-1][j][0]
• 昨天持有，今天卖出了：dp[i-1][j][1] + prices[i]（卖出得到现金，所以加价格）

取两者中利润大的。

注意：卖出操作不消耗交易次数。因为交易次数是在买入时减少的（一次交易=买入+卖出，我们在买入时扣减次数）。

第二行：今天持有股票 也有两种可能：

• 昨天就持有，今天没操作：dp[i-1][j][1]