力扣188-买卖股票的最佳时机 IV（Java详细题解）

题目链接：188. 买卖股票的最佳时机 IV - 力扣（LeetCode）

前情提要：

本题是由123. 买卖股票的最佳时机 III - 力扣（LeetCode）变形而来，123是只能买卖俩次股票，该题是只能买卖k次股票，我相信当你做完这道题或者看完我上道题的题解，那么写这道题会轻松一点。

因为本人最近都来刷dp类的题目所以该题就默认用dp方法来做。

dp五部曲。

1.确定dp数组和i下标的含义。

2.确定递推公式。

3.dp初始化。

4.确定dp的遍历顺序。

5.如果没有ac打印dp数组 利于debug。

每一个dp题目如果都用这五步分析清楚，那么这道题就能解出来了。

题目思路:

该题与买卖股票的最佳时机 III ，唯一区别就是控制了买卖的次数为k。那我们就需要2k个状态来表示他所有的状态。

k是题目给出的，所以我们必须找一个规律，用一个统一的公式来表示买卖股票的k次状态。

其实买卖股票的最佳时机 III已经给了我们启示。

dp[i] [0] = 0

dp[i] [1] = Math.max(dp[i-1] [0] - prices[i], dp[i - 1 ] [1]);

dp[i] [2] = Math.max(dp[i - 1] [1] + prices[i], dp[i - 1] [2])

dp[i] [3] = Math.max(dp[i - 1] [3], dp[i - 1] [2] - prices[i]);

dp[i] [4] = Math.max(dp[i - 1] [4], dp[i - 1] [3] + prices[i]);

我们用j来控制第几次买卖股票。

你会发现当j为奇数的时候。

dp[i] [j] = Math.max(dp[ i - 1] [j],dp[ i - 1] [j - 1] - prices[i])；

每一次的持股的手上的最大现金要么是延续上一天状态（上一天持股的手上的最大现金）。

要么是当次买入股票，需要上一次买卖股票所得的现金再减去这次买入股票的现金。

第一次的dp[i-1] [0]就是相等于 0 ，也就是第一买入股票就等于 0 - 这次买入股票的现金。

你会发现当j为偶数的时候。

dp[i] [j] = Math.max(dp[ i - 1] [j],dp[ i - 1] [j - 1] + prices[i])；

每一次的不持股的手上的最大现金要么是延续上一天状态（上一天不持股的手上的最大现金）。

要么是当次卖出股票，需要上一次买股票所得的现金加上去这次卖出股票的现金。

所以这样我们就能得出买卖为k次的所有状态。

接下来我们用dp五部曲来系统分析一下。

1.确定dp数组和i下标的含义。

dp[i] [j + 1] 表示的就是下标为i天不持股的手上的最大现金

dp[i] [j + 2] 表示的就是下标为i天持股的手上的最大现金

为什么要用j + 1表示不持股 j + 2表示持股呢?

我不能用j吗。

注意看dp数组的定义，dp[i] [0]的状态是不操作 dp[i] [1]才表示第一次持股，而我们的j是从0开始遍历。

所以要用j + 1表示不持股 j + 2表示持股。

那么就这样定义dp数组。

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

2.确定递推公式。

经过上述分析后我们可以推导出一个规律方程。

//这里我们用j来控制每次买卖股票的状态 每次 j += 2就跳转到下一次买卖
for (int j = 0; j < 2 * k - 1; j += 2) {
    dp[i][j + 1] = max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]);
    dp[i][j + 2] = max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]);
}

3.dp初始化。

dp[0] [j]是递推的起始位置，所以我们要初始化dp[0] [j]。

dp[0] [1] 表示下标为0天第一次持股 那肯定就是当天买入股票 就为 -prices[0]

dp[0] [2] 表示下标为0天第一次不持股 那就是当天买入股票再卖出 就为0

dp[0] [3] 表示下标为0天第二次持股 那就是第一买卖结束后 再买入股票 也是 -prices[0]

dp[0] [4] 表示下标为0天第二次不持股 当天第二次买入股票再卖出 也为0

由此也可以看出 j 为奇数时都初始化为 -prices[0] 为偶数时初始化为0

//Java默认数组初始化为0 所以为0的情况可以不用处理
for (int j = 1; j < 2 * k; j += 2) {
    dp[0][j] = -prices[0];
}

4.确定dp的遍历顺序。

从递推公式其实已经可以看出，一定是从前向后遍历，因为dp[i]，依靠dp[i - 1]的数值。

5.如果没有ac打印dp数组 利于debug。

最终代码：

class Solution {
    public int maxProfit(int k, int[] prices) {
        //该题其实就是买卖股票的最佳时机三的变形，该题是指定买卖k次,所以我们需要2k个状态.
        //那我们手写2k个状态吗，肯定不可能。
        //所以我们就要找规律，抽象出一个规律方程来
        //我们用j来控制每一次买卖股票的dp数组 那么j就能表示k次买卖了 由于每次买卖都需要俩个状态 所以每次 j+=2 就能进入下一次买卖
        //由于j 从 0 开始
        //所以每次买卖中 j + 1就表示持股手上的最大现金  j + 2就表示不持股手上的最大现金
        //dp数组定义
        int [][] dp = new int [prices.length + 1][2 * k + 1];
        //dp的初始化 只有在持股的时候就会将下标0天的股票买入
        for(int j = 1;j < 2 * k;j += 2){
            dp[0][j] = -prices[0];
        }
        //dp的遍历顺序
        for(int i = 1;i < prices.length;i ++){
            for(int j = 0;j < 2 * k;j += 2){
                dp[i][j + 1] = Math.max(dp[i - 1][j + 1],dp[i - 1][j] - prices[i]);
                dp[i][j + 2] = Math.max(dp[i - 1][j + 2],dp[i - 1][j + 1] + prices[i]);
            }
        }
        return dp[prices.length - 1][2 * k];

    }
}

这一篇博客就到这了，如果你有什么疑问和想法可以打在评论区，或者私信我。

我很乐意为你解答。那么我们下篇再见！