动态规划之股票问题123

问题描述:

给定一个数组,它的第 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])

 

 

 

 

上一篇:vue-cli3总结


下一篇:面试题 17.16. 按摩师(C++)