尘雨尘风

数学与编程的爱好者

0%

leetcode题解122：买卖股票的最佳时机 II

发表于 分类于
本文字数： 1.3k 阅读时长 ≈ 1 分钟

描述

该题来自于力扣第122题

分析

股票问题有很多遍历，没有通用的解决思路的话确实有点难度，类似背包问题，考虑动态规划，状态是第i天是否持有股票的最大收益，如dp[i][0]表示第i天不持有股票的最大收益，dp[i][1]表示第i天持有股票的最大收益，接下来主要分析状态转移过程：

  1. 第i天不持有，有两种情况：（a）第i-1天不持有，（b）第i-1天持有，表示第i天卖出股票，从而收益增加prices[i]；从而dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])；
  2. 第i天持有，也有两种情况：（a）第i-1天持有，（b）第i-1天不持有，表示第i-1天买入，从而收益减少prices[i]；从而dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])；

上述转移方程非常重要，是解所有这种类型题的关键，比如该题的解决方法，可以看到状态只依赖上次的状态，从而设dp0为当天不持有股票的最大收益，dp1为当天持有股票的最大收益，从而转移方程为

1
2
3
new_dp0 = max(dp0, dp1 + prices[i])
new_dp1 = max(dp1, dp0 - prices[i])
dp0, dp1 = new_dp0, new_dp1

而边界条件可以直接考虑，第0天不持有显然收益为0，从而dp0 = 0，而持有收益显然为-prices[0]；最终结果显然是最后一天不持有股票的收益最大即dp1。

代码

1
2
3
4
5
6
7
8
9
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        dp0 = 0
        dp1 = -prices[0]
        for i in range(1, len(prices)):
            new_dp0 = max(dp0, dp1 + prices[i])
            new_dp1 = max(dp1, dp0 - prices[i])
            dp0, dp1 = new_dp0, new_dp1
        return dp0

附录：通用解法

如果加上条件，最多只能交易k次，求最大收益，那么用dp[i][k][0],dp[i][k][1]分别表示在i天交易了k次不持有和持有的最大收益，由于最多只能持有一支股票，从而买入卖出操作必须一起，为了方便，将买入作为交易次数的记录，从而转移方程为

1
2
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])  # 由于买入算交易依次，从而是k-1次不持有的状态

而这一题没有限制次数，从而\(k = + \infty\)，转移方程就简化为

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

  • 至多k次和交易满k次结果是一样的，因为如果不满k次，可以在同一天买入卖出无限次，收益保持不变。
相关文章