代码随想录算法训练营第四十天

代码随想录算法训练营第四十天 | 股票问题

LeetCode 121.买卖股票的最佳时机：

文章链接
题目链接：121.买卖股票的最佳时机

思路

方法1：暴力

看到题目最直接的想法是双层遍历求最大区间差

class Solution:def maxProfit(self, prices):if len(prices) <= 1:return 0result = 0for i in range(len(prices)):for j in range(i + 1, len(prices)):result = max(result, prices[j] - prices[i])return result

这种方法的时间复杂度为O(n^2)，会超时

方法2：贪心

一次遍历，向左求最小值，向右求最大值，再用求得的两个值求差。
或者，也可以这样，一次遍历过程中，更新最小值，同时更新 result 为max(prices[i] - 最小值，result)。

class Solution:def maxProfit(self, prices: List[int]) -> int:if len(prices) <= 1:return 0low, result = float('inf'), 0for price in prices:low = min(low, price)   # 向左找最小值result = max(result, price - low)   # 直接取最大区间利益return result

方法3：动态规划

因为需要考虑是否买入股票和卖出股票，所以对应的dp数组为二维数组，分别保存当前持有股票和没持有股票得到的利润（持有可能是之前买入了，不一定是当前买入）
动规五部曲：

dp数组及含义：
dp[i][0]表示当前持有股票的利润，dp[i][1]表示当前没持有股票所获得的利润。
可以理解最开始现金为0，因此持有股票时，利润为 - prices[j]，即股票价格的负数
递推公式：
dp[i][0]的来源：
① 上一天持有股票，dp[i - 1][0]
② 上一天不持有股票，今天买入了股票，-prices[i]
因为是获取的最大利润，所以是求max（也可以理解上面这个过程是在求最低的股票价格）
dp[i][1]的来源：
① 上一天持有股票，今天卖出去了，利润为prices[i] + dp[i - 1][0]（[0]是负的）
② 上一天不持有股票，利润为dp[i - 1][1]
也是求max
初始化
由递推公式可知，dp[i]只与dp[i - 1]有关，因此初始化dp[0]，第1天持有股票，只可能是第1天买入，dp[0][0] = -prices[0]，第1天不持有股票，利润自然是0，dp[0][1] = 0
遍历顺序
从前往后
举例
最后最大利润是dp[len - 1][1]，因为dp[0]一定小于0

class Solution:def maxProfit(self, prices: List[int]) -> int:if len(prices) <= 1:return 0dp = [[0,0] for _ in range(len(prices))]# 初始化dp[0][0] = -prices[0]dp[0][1] = 0# 遍历for i in range(1, len(prices)):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]

仔细研究递推式会发现，dp[i]只与dp[i - 1]有关，因此dp数组可以缩小为2*2的数组

class Solution:def maxProfit(self, prices: List[int]) -> int:if len(prices) <= 1:return 0len_prices = len(prices)dp = [[0, 0], [0, 0]]# 初始化dp[0][0] = -prices[0]dp[0][1] = 0# 遍历for i in range(1, len_prices):dp[i % 2][0] = max(dp[(i - 1) % 2][0], -prices[i])dp[i % 2][1] = max(dp[(i - 1) % 2][1], prices[i] + dp[(i - 1) % 2][0])return dp[(len_prices - 1) % 2][1]

LeetCode 122.买卖股票的最佳时机Ⅱ：

文章链接
题目链接：122.买卖股票的最佳时机Ⅱ

思路

方法1：贪心

之前用过，基本思路是：昨天买入，今天卖出。如果亏了，就当作昨天没买入，不算入利润；赚了就算入利润。然后除最后一天外都会买入

class Solution:def maxProfit(self, prices: List[int]) -> int:if len(prices) <= 1:return 0maxprofit = 0preprice = prices[0]for price in prices[1:]:maxprofit += max(0, price - preprice)preprice = pricereturn maxprofit

方法2：动态规划：

首先弄清楚本题与上题的区别，上题是股票只有一次买入和卖出的机会，这次是股票可以经历多次买入和卖出。
动规五部曲中，dp数组及含义是相同的，递推式有不同，因为可以多次买入和卖出，因此dp[i][0]
① 昨天持有股票：dp[i - 1][0]
② 昨天没持有股票：之前的题目，如果昨天没持有股票，那么认为之前利润为0，更新的利润为 - prices[i]；而这道题，昨天没有持有股票可能是昨天卖出去，已经有了一部分利润，因此为 dp[i - 1][1] - prices[i] （且上道题的递推式不能用这道题的）
其余相同
举例：
到最后获得最大利润一定是手上没有股票了
在这里插入图片描述

"""
也可以像上一题一样把dp变成2*2的数组，因为递推式dp[i]还是只与dp[i - 1]有关
"""
class Solution:def maxProfit(self, prices: List[int]) -> int:if len(prices) <= 1:return 0len_prices = len(prices)dp = [[0, 0] for _ in range(len_prices)]# 初始化dp[0][0] = -prices[0]   # 持有股票的利润# 遍历for i in range(1, len_prices):dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i])  # 持有股票，注意这个地方dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i])  # 不持有股票return dp[len_prices - 1][1]

LeetCode 123.买卖股票的最佳时机Ⅲ：

文章链接
题目链接：123.买卖股票的最佳时机Ⅲ

思路：

首先分析题目，题目要求最多可以完成两笔交易，因此在原来分是否持有的基础上，需要继续分为是第一次还是第二次。
动规五部曲：

dp数组及含义：
dp[i]应当有4列，dp[i][0]为第一次持有，dp[i][1]为第一次不持有，dp[i][2]为第二次持有，dp[i][3]为第二次不持有。后面接的都是最大利润。
注意：持有不是当天买入，之前买入，现在不卖出也是持有
递推公式：
- dp[i][0]：
  第一次持有，如果昨天持有：dp[i - 1][0]；如果昨天没持有，今天买入：-prices[i]（因为是第一次，所以前面没有利润）
- dp[i][1]：
  昨天持有，今天卖出：dp[i - 1][0] + prices[i]
  昨天没持有：dp[i - 1][1]
- dp[i][2]：
  昨天持有：dp[i - 1][2]
  昨天没持有，今天买入（第二次，之前有利润）：dp[i - 1][1] - prices[i]
- dp[i]][3]：
  昨天持有，今天卖出：dp[i - 1][2] + prices[i]
  昨天没持有：dp[i - 1][3]
  并且都是求最大值
初始化：
由递推公式可知，应当初始化dp[0]，因为是第一天，只要是买入，不管第几次买入，都是-prices[0]，只要是卖出，肯定是当天买入当天卖出，都是0
遍历方式：
从前往后
举例
最后求的最大利润一定是dp[-1][3]的值，判断原因如下：
① 如果是一次买入卖出就得到了最大值，那第二次买入卖出肯定是都是当天，因此dp[-1][1] 等于dp[-1][3]
② 如果是两次买入卖出得到最大值，那也就是dp[-1][3]的值

class Solution:def maxProfit(self, prices: List[int]) -> int:if len(prices) <= 1:return 0# 初始化len_prices = len(prices)dp = [[0,0,0,0] for _ in range(len_prices)]dp[0][0] = dp[0][2] = -prices[0]# 遍历for i in range(1, len_prices):dp[i][0] = max(dp[i - 1][0], -prices[i])    # 第一次买入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])  # 第二次卖出return dp[len_prices - 1][3]