题目描述

题解

动态规划

因为有交易次数k的限制, 首先需要判断的一点是，一次交易至少需要 2 天，一天买，一天卖。因此如果 k 很大，大到大于等于 len / 2，就相当于股票系列的第 2 题，使用贪心算法去做就可以了。这是一个特判。

这道题用动态规划完成，比之前的股票问题多一个限制，则有后效性，因此可以多设置一个状态去消除这种后效性。

“无后效性”有两层含义：（1）当前做的决策一旦确定，后面的决策不会影响到之前决策的结果；（2）当前决策得到一个最优值，这个最优值怎么来的，后面的决策并不关心。

第 1 步：状态定义

比较容易想到的是：先阶段，即第几天，然后是状态 1，即处在第几个交易，再是状态 2，即现在是持股还是不持股。

设置持股的状态值为 1，不持股的时候，状态值为 0。

为此设计状态如下：

dp[i][j][K] ：表示到第 i 天为止，已经交易了 j 次，并且当前持股状态为 K 的最大收益。

第 2 步：状态转移方程

下面考虑 dp[i][j][0] 和 dp[i][j][1] 可以怎样转移过来。

动态规划用于解决多阶段的决策问题，这里的阶段就是每一天，因此，状态都是从前一天的某一个之前的状态转移过来。

dp[i][j][0]：表示这一天发生了第 j 次交易（从 0 开始），并且不持股。

我是这样定义交易行为的：发生交易的标志是在某一天有了一次购买股票的行为，视为发生一次交易。发生一次抛售股票的行为，认为和上一次购买股票在一次交易行为内。

分类讨论的依据是：昨天是否持股。

（1）昨天不持股，今天还不持股，说明没有发生新的交易；

（2）昨天持股，今天不持股，说明这次交易结束了。这两种情况都在一次交易里。

1	dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i])

注意：中间的那个表示交易次数的状态都是 j。

dp[i][j][1]：表示这一天发生了第 j 次交易（从 0 开始），并且持股。

分类讨论的依据依然是：昨天是否持股。

（1）昨天持股，今天还持股，说明没有发生新的交易，这两天在同一个交易区间里；

（2）昨天不持股，今天持股，说明开启了一次新的交易。

1	dp[i][j][1] = max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i])

第 3 步：初始化

所有不持股的状态值初始化的时候为 0。所有持股的状态值都设置为一个很大的负数（至少应该是最大的股价的负数 - 1），表示未知。

第 4 步：输出

public class lc188 {
    public int maxProfit(int k, int[] prices) {
        int len = prices.length;

        if (len < 2 || k == 0) {
            return 0;
        }

        if (k >= len / 2) {
            return greedy(prices, len);
        }

        int[][][] dp = new int[len][k][2];

        for (int i = 0; i < len; i++) {
            for (int j = 0; j < k; j++) {
                dp[i][j][1] = Integer.MIN_VALUE;
            }
        }

        for (int i = 0; i < len; i++) {
            for (int j = 0; j < k; j++) {
                if (i == 0) {
                    dp[i][j][1] = -prices[0];
                    dp[i][j][0] = 0;
                } else {
                    if (j == 0) {
                        dp[i][j][1] = Math.max(dp[i - 1][j][1], -prices[i]);
                    } else {
                        dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]);
                    }
                    dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);
                }
            }
        }
        return dp[len - 1][k - 1][0];

    }

    private int greedy(int[] prices, int len) {
        int res = 0;

        for (int i = 0; i < len - 1; i++) {
            if (prices[i] < prices[i + 1]) {
                res += prices[i + 1] - prices[i];
            }
        }

        return res;
    }
}