问题描述:
给定一个数组,它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意: 你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
示例:
输入: [3,3,5,0,0,3,1,4]
输出: 6
解释: 在第 4 天(股票价格 = 0)的时候买入,在第 6 天(股票价格 = 3)的时候卖出,这笔交易所能获得利润 = 3-0 = 3 。
随后,在第 7 天(股票价格 = 1)的时候买入,在第 8 天 (股票价格 = 4)的时候卖出,这笔交易所能获得利润 = 4-1 = 3
分析:
又加了一个限制,只能购买两次,这已然难不倒我们,我们只需要把第 i 天,第 j 次交易完成后的收益记录下来了。
设dp0[m][n],为第 i 天, 第 j 次交易,且手中没有没有股票(卖出)
设dp1[m][n],为di i 天,第 j 次交易,且手中有股票(买入)
这里第 i 天卖出股票的的状态不仅和 第 i - 1天的买入有关系,还和 j - 1 次交易有关系。
第 i 天买入的状态只和上一次交易完成时的状态有关,上一次交易完成了,就不会干扰到新的交易。
得出dp方程
dp0[i][j] = max(dp0[i][j], dp1[i-1][j-1] + price[i])
dp1[i][j] = max(dp1[i][j], dp0[i-1][j] - price[i])
上代码:
class Solution:
def maxProfit(self, prices: List[int]) -> int:
# dp[i][j] i 天,j次
# dp0 手头没有股票
# dp1 手头有股票
dp0 = [[0]*3 for _ in range(len(prices))]
dp1 = [[0]*3 for _ in range(len(prices))]
for j in range(3):
dp1[0][i] = -prices[0]
for i in range(1, len(prices)):
dp1[i][0] = max(dp1[i-1][0], -prices[i])
for j in range(1,3):
dp0[i][j] = max(dp0[i-1][j], dp1[i-1][j-1] + prices[i])
dp1[i][j] = max(dp1[i-1][j], dp0[i-1][j] - prices[i])
for i in range(len(dp0)):
print(dp0[i])
return dp0[-1][-1]
说明:一次交易都没完成的时候,也就是需要买入股票,所以需要初始化dp1[i][0] = max(dp1[i-1][0], -prices[i])