代码随想录算法训练营第四十二天|121. 买卖股票的最佳时机，122.买卖股票的最佳时机II

作者：木道寻08 | 2024-08-23 07:46:13

踩

系列文章目录

文章目录

系列文章目录
121. 买卖股票的最佳时机
122.买卖股票的最佳时机II

121. 买卖股票的最佳时机

题目链接： 121. 买卖股票的最佳时机
题目内容： 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
视频讲解： 动态规划之 LeetCode：121.买卖股票的最佳时机1

动态规划问题的五步曲：

确定dp数组（dp table）以及下标的含义：dp[i][0] 表示第i天持有股票所得最多现金，dp[i][1] 表示第i天不持有股票所得最多现金
确定递推公式：
- 如果第i天持有股票即dp[i][0]，那么可以由两个状态推出来：第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金即：dp[i - 1][0]；第i天买入股票，所得现金就是买入今天的股票后所得现金即：-prices[i]；那么dp[i][0]应该选所得现金最大的，所以dp[i][0] = max(dp[i - 1][0], -prices[i]);
- 如果第i天不持有股票即dp[i][1]，也可以由两个状态推出来：第i-1天就不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金即：dp[i - 1][1]；第i天卖出股票，所得现金就是按照今天股票价格卖出后所得现金即：prices[i] + dp[i - 1][0]；同样dp[i][1]取最大的，dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);
dp数组如何初始化：
- dp[0][0]表示第0天持有股票，此时的持有股票就一定是买入股票了，所以dp[0][0] -= prices[0]；
- dp[0][1]表示第0天不持有股票，不持有股票那么现金就是0，所以dp[0][1] = 0;
确定遍历顺序：从前到后遍历
举例推导dp数组

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        length=len(prices)
        if length == 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]
1
2
3
4
5
6
7
8
9
10
11
12

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

题目链接： 122.买卖股票的最佳时机II
题目内容： 给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。在每一天，你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。你也可以先购买，然后在同一天出售。返回你能获得的最大利润。
视频讲解： 动态规划，股票问题第二弹 | LeetCode：122.买卖股票的最佳时机II

122.买卖股票的最佳时机II与121. 买卖股票的最佳时机的区别主要体现在动规五部曲的递推公式上：

如果第i天持有股票即dp[i][0]，那么可以由两个状态推出来
- 第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金即：dp[i - 1][0]
- 第i天买入股票，所得现金就是昨天不持有股票的所得现金减去今天的股票价格即：dp[i - 1][1] - prices[i]
如果第i天不持有股票即dp[i][1]的情况，依然可以由两个状态推出来
- 第i-1天就不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金即：dp[i - 1][1]
- 第i天卖出股票，所得现金就是按照今天股票价格卖出后所得现金即：prices[i] + dp[i - 1][0]

代码几乎一样，唯一的区别在：

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

这是因为本题的股票可以买卖多次，所以买入股票的时候，可能会有之前买卖的利润即：dp[i - 1][1]，所以dp[i - 1][1] - prices[i]。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        length=len(prices)
        if length == 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],dp[i-1][1]-prices[i])
            dp[i][1]=max(dp[i-1][1],prices[i]+dp[i-1][0])
        return dp[-1][1]
1
2
3
4
5
6
7
8
9
10
11
12

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/木道寻08/article/detail/1020089