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]

最后更新于