2024/06/18--代码随想录算法8/17| 股票问题

121.买卖股票的最佳时机

力扣链接

动规五部曲

1. 确定dp数组（dp table）以及下标的含义
   dp[i][0] 表示第i天持有股票所得最多现金,dp[i][1] 表示第i天不持有股票所得最多现金
2. 确定递推公式
   
   dp[i][0] = max(dp[i-1][0], -price[i])
   dp[i][1]=max(dp[i-1][1], dp[i-1][0]+price[i])
3. dp数组初始化
   那么dp[0][0]表示第0天持有股票，此时的持有股票就一定是买入股票了，因为不可能有前一天推出来，所以dp[0][0] -= prices[0];
   dp[0][1]表示第0天不持有股票，不持有股票那么现金就是0，所以dp[0][1] = 0;
4. 遍历顺序 ：dp[i]都是由dp[i - 1]推导出来的，那么一定是从前向后遍历。
   股票只能买入一次，卖出一次，要先买，才能卖，
   dp[i][0] = max(dp[i-1][0], -prices[i])，而不是max（dp[i-1][0], dp[i-1][1]-prices[i]）

动态规划

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

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        length = len(prices)
        dp0, dp1 = -prices[0], 0 #注意这里只维护两个常量，因为dp0的更新不受dp1的影响
        for i in range(1, length):
            dp1 = max(dp1, dp0 + prices[i])
            dp0 = max(dp0, -prices[i])
        return dp1

贪心法

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        low = float("inf")
        result = 0
        for i in range(len(prices)):
            low = min(low, prices[i]) #取最左最小价格
            result = max(result, prices[i] - low) #直接取最大区间利润
        return result

122.买卖股票的最佳时机II

力扣链接

动规五部曲

1. 确定dp数组（dp table）以及下标的含义
   dp[i][0] 表示第i天持有股票所得最多现金,dp[i][1] 表示第i天不持有股票所得最多现金
2. 确定递推公式
   dp[i][0] = max(dp[i-1][0], dp[i-1][1]-price[i])
   dp[i][1]=max(dp[i-1][1], dp[i-1][0]+price[i])
3. dp数组初始化
   那么dp[0][0]表示第0天持有股票，此时的持有股票就一定是买入股票了，因为不可能有前一天推出来，所以dp[0][0] -= prices[0];
   dp[0][1]表示第0天不持有股票，不持有股票那么现金就是0，所以dp[0][1] = 0;
4. 遍历顺序
   和上一题的区别在于，本题股票可以买卖多次

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

时间复杂度：O(n) 空间复杂度：O(n)

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        length = len(prices)
        dp = [[0] * 2 for _ in range(length)]
        dp[0][0] = -prices[0]
        dp[0][1] = 0
        for i in range(1, length):
            dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i]) #注意这里是和121. 买卖股票的最佳时机唯一不同的地方
            dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i])
        return dp[-1][1]

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

力扣链接

动规五部曲

1. 确定dp数组（dp table）以及下标的含义
   
2. 确定递推公式
   dp[i][1]=max(dp[i-1][1], -price[i])
   dp[i][2]=max(dp[i-1][2], dp[i-1][1]+price[i])
   dp[i][3] = max(dp[i-1][3], dp[i-1][2]-price[i])
   dp[i][4] = max(dp[i-1][4],dp[i-1][3]+price[i])
3. dp数组初始化
   那么dp[0][0]表示第0天持有股票，所以dp[0][0] = -prices[0];
   dp[0][1]表示第0天不持有股票，不持有股票那么现金就是0，所以dp[0][1] = 0;
   dp[0][3] = -prices[0]
   dp[0][4] = 0
4. 遍历顺序 ：dp[i]都是由dp[i - 1]推导出来的，那么一定是从前向后遍历。
   股票至多买卖两次，可以买卖2次，买卖1次，或者不买卖
   第二次必须在第一次之后后面，控制dp[i][3] = max(dp[i-1][3], dp[i-1][2] - prices[i])，而不是dp[i][3] = max(dp[i-1][3], dp[i-1][4] - prices[i])，后面这种是两个独立的一次买卖
   现在最大的时候一定是卖出的状态，而两次卖出的状态现金最大一定是最后一次卖出。如果想不明白的录友也可以这么理解：如果第一次卖出已经是最大值了，那么我们可以在当天立刻买入再立刻卖出。所以dp[4][4]已经包含了dp[4][2]的情况。也就是说第二次卖出手里所剩的钱一定是最多的。

时间复杂度：O(n) 空间复杂度：O(n × 5)

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

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