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

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/

解法一：dp

思路：利用「状态」进行穷举。具体到每一天，看看总共有几种可能的「状态」，再找出每个「状态」对应的「选择」。

这类股票问题，每天都有三种「选择」：买入、卖出、无操作，我们用 buy, sell, rest 表示，因为 sell 必须在 buy 之后，buy 必须在 sell 之后。那么 rest 操作还应该分两种状态，一种是 buy 之后的 rest（持有了股票），一种是 sell 之后的 rest（没有持有股票）。而且还有交易次数 k 的限制，即 buy 还只能在 k > 0 的前提下操作。

由于有三种“状态”，因此用三维数组表示，第一维是天数，第二维是允许交易的最大次数，第三维是当前的持有状态（即 rest ，用 1 表示持有，0 表示不持有）例如 dp[3][2][1] 的含义就是：今天是第三天，我现在手上持有着股票，至今最多进行 2 次交易。再比如 dp[2][3][0] 的含义：今天是第二天，我现在手上没有持有股票，至今最多进行 3 次交易。

我们想求的最终答案是 dp[n - 1][K][0]，即最后一天，最多允许 K 次交易，最多获得多少利润。可能问为什么不是 dp[n - 1][K][1]？因为 dp[n - 1][K][1] 代表到最后一天手上还持有股票，dp[n - 1][K][0] 表示最后一天手上的股票已经卖出去了，很显然后者得到的利润一定大于前者。

第i天操作k次，不持有股票的状态转移方程：

dp[i][k][0] = max(dp[i-1][k][0]    , dp[i-1][k][1] + prices[i])
              max(   不卖——`rest`   ,         卖—— `sell`      )

第i天操作k次，仍持有股票（这里交易次数为k-1，因为买卖合起来算一次交易，上面卖的时候没算，因此在这里买的时候算。算在卖的时候也等效）：

dp[i][k][1] = max(dp[i-1][k][1]   , dp[i-1][k-1][0] - prices[i])
              max(   不买——`rest`  ,           买——`buy`        )

再考虑初始条件：

dp[-1][k][0] = 0
解释：因为 i 是从 0 开始的，所以 i = -1 意味着还没有开始，这时候的利润当然是 0 。
dp[-1][k][1] = -infinity
解释：还没开始的时候，是不可能持有股票的。
因为我们的算法要求一个最大值，所以初始值设为一个最小值，方便取最大值。
dp[i][0][0] = 0
解释：因为 k 是从 1 开始的，所以 k = 0 意味着根本不允许交易，这时候利润当然是 0 。
dp[i][0][1] = -infinity
解释：不允许交易的情况下，是不可能持有股票的。
因为我们的算法要求一个最大值，所以初始值设为一个最小值，方便取最大值。

总结

初始条件：
dp[-1][k][0] = dp[i][0][0] = 0
dp[-1][k][1] = dp[i][0][1] = -infinity

状态转移方程：
0 <= i <= n-1, 1 <= k <= K
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])

因为i=-1不方便操作，这里用i=0表示初始状态（第0天，还未开始），因为i从第1天开始，而prices数组从0开始，所以第i天的股价为prices[i-1]

j取值0 ≤ j ≤ k。

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        n = len(prices)
        if k == 0  or n == 0:
            return 0
        #三维数组
        dp = [[[0] * 2 for _ in range(k + 1)] for _ in range(n+1)]

        for i in range(n + 1):
            for j in range(k + 1):
                #对i==0和j==0的边界条件做特殊处理，不更新dp
                if i == 0:
                    dp[i][j][0] = 0
                    dp[i][j][1] = -sys.maxsize
                    continue
                if j == 0:
                    dp[i][j][0] = 0
                    dp[i][j][1] = -sys.maxsize
                    continue
                dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i-1])
                dp[i][j][1] = max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i-1])
        return dp[n][k][0]