代码随想录 动态规划 Ⅹ

123. 买卖股票的最佳时机 III

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

思路：最多可以完成两笔，也就是说在一天之中，可能存在五个状态：从未持有过股票，买入第一支股票，卖出第一支股票且未买入第二支股票，买入第二只股票，卖出第二支股票，那么可以建立一个 len（prices）* 5 大小的数组，dp[i][x]表示在第i天第x个状态下的最大利润。转移方程为 dp[i][0] = 0，dp[i][1] = max(dp[i-1][0], dp[i-1][0] - price[i]), dp[i][2] = max(dp[i-1][2], dp[i-1][1] + prices[i]) 以此类推 , 初始状态为：dp[i][0] = dp[i][2]=dp[i][4]= 0, dp[i][1] = dp[i][3]= - price[0]

python: 

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        dp = [[0] * 5 for _ in range(len(prices))]
 
        dp[0][1] = dp[0][3] = -prices[0]
 
        for i in range(1, len(prices)):
            dp[i][0] = 0
            dp[i][1] = max(dp[i-1][0] - prices[i], dp[i-1][1])
            dp[i][2] = max(dp[i-1][1] + prices[i], dp[i-1][2])
            dp[i][3] = max(dp[i-1][2] - prices[i], dp[i-1][3])
            dp[i][4] = max(dp[i-1][3] + prices[i], dp[i-1][4])
 
        return dp[-1][4]

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

思路：与上一题思路类似 

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        dp = [[0] * (2*k+1) for _ in range(len(prices))]
      
 
        for j in range(2*k + 1):
            if j % 2 == 1:
                dp[0][j] = -prices[0]
 
        for i in range(1, len(prices)):
            for n in range(1, 2*k+1):
                if n % 2 == 1:
                    dp[i][n] = max(dp[i-1][n], dp[i-1][n-1] - prices[i])
                
                else:
                    dp[i][n] = max(dp[i-1][n], dp[i-1][n-1] + prices[i])
        
        return dp[-1][-1]