代码随想录算法训练营Day35 | Leetcode121.买卖股票的最佳机遇、122.买卖股票的最佳机遇II、123.买卖股票的最佳机遇III
一、买卖股票的最佳机遇
相干题目：Leetcode121
文档讲解：Leetcode121
视频讲解：Leetcode121
1. Leetcode121. 买卖股票的最佳机遇
给定一个数组 prices ，它的第 i 个元素 prices 表现一支给定股票第 i 天的代价。你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。计划一个算法来盘算你所能获取的最大利润。返回你可以从这笔生意业务中获取的最大利润。假如你不能获取任何利润，返回 0 。
提示：
- 1 <= prices.length <= 105
- 0 <= prices <= 104
- 思绪：
- 贪婪：由于股票就买卖一次，那么贪婪的想法很自然就是取最左最小值，取最右最大值，那么得到的差值就是最大利润。
- 动规五部曲：
- 确定 dp 数组以及下标的寄义：dp[0] 表现第 i 天持有股票所得最多现金 ，一开始现金是 0，那么参加第 i 天买入股票现金就是 -prices。dp[1] 表现第 i 天不持有股票所得最多现金。
- 确定递推公式：
- 假如第 i 天持有股票即 dp[0]，可以由两个状态推出来：
- 第 i-1 天就持有股票，那么保持现状，所得现金就是昨天持有股票的所得现金，即：dp[i - 1][0]。
- 第 i 天买入股票，所得现金就是买入本日的股票后所得现金即：-prices。
则 dp[0] 应该选所得现金最大的，所以 dp[0] = max(dp[i - 1][0], -prices)。
- 假如第 i 天不持有股票即 dp[1]， 也可以由两个状态推出来：
- 第 i-1 天就不持有股票，那么保持现状，所得现金就是昨天不持有股票的所得现金 即：dp[i - 1][1]。
- 第 i 天卖出股票，所得现金就是按照本日股票代价卖出后所得现金即：prices + dp[i - 1][0]。
则 dp[1] 应该选所得现金最大的，所以 dp[1] = max(dp[i - 1][1], prices + dp[i - 1][0])。
- dp 数组怎样初始化：由递推公式可以看出其基础都是要从 dp[0][0] 和 dp[0][1] 推导出来，那么 dp[0][0] 表现第 0 天持有股票，此时的持有股票就一定是买入股票了，由于不可能有前一天推出来，所以 dp[0][0] -= prices[0]；dp[0][1]表现第 0 天不持有股票，不持有股票那么现金就是 0，所以 dp[0][1] = 0。
- 确定遍历次序：从递推公式可以看出 dp 都是由 dp[i - 1] 推导出来的，那么一定是从前向后遍历。
- 举例推导 dp 数组：以输入 [7,1,5,3,6,4] 为例，dp 数组状态如下：
- 贪婪
- 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
- ###动态规划：版本一
- 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]
-
- ###动态规划：版本二
- class Solution:
- def maxProfit(self, prices: List[int]) -> int:
- length = len(prices)
- dp = [[0] * 2 for _ in range(2)] #注意这里只开辟了一个2 * 2大小的二维数组
- dp[0][0] = -prices[0]
- dp[0][1] = 0
- for i in range(1, length):
- 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[(length-1) % 2][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
相干题目：Leetcode122
文档讲解：Leetcode122
视频讲解：Leetcode122
1. Leetcode122.买卖股票的最佳机遇II
给你一个整数数组 prices ，其中 prices 表现某支股票第 i 天的代价。
在每一天，你可以决定是否购买和/或出售股票。你在任何时间 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
返回 你能获得的 最大 利润 。
提示：
- 1 <= prices.length <= 3 * 104
- 0 <= prices <= 104
- 思绪：
- 本题和 Leetcode121. 买卖股票的最佳机遇 的唯一区别是本题股票可以买卖多次了，在动规五部曲中，区别主要是体如今递推公式上。
- 递推公式：
- 假如第 i 天持有股票即 dp[0]， 那么可以由两个状态推出来：
- 第 i-1 天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即：dp[i - 1][0]。
- 第 i 天买入股票，所得现金就是昨天不持有股票的所得现金减去本日的股票代价 即：dp[i - 1][1] - prices（ Leetcode121. 买卖股票的最佳机遇 中为 -prices）。
- 假如第 i 天不持有股票即 dp[1]， 依然可以由两个状态推出来：
- 第 i-1 天就不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金 即：dp[i - 1][1]。
- 第 i 天卖出股票，所得现金就是按照本日股票代价卖出后所得现金即：prices + dp[i - 1][0]。
- 动态规划
- ###版本一
- 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]
-
- ###版本二：
- class Solution:
- def maxProfit(self, prices: List[int]) -> int:
- length = len(prices)
- dp = [[0] * 2 for _ in range(2)] #注意这里只开辟了一个2 * 2大小的二维数组
- dp[0][0] = -prices[0]
- dp[0][1] = 0
- for i in range(1, length):
- dp[i % 2][0] = max(dp[(i-1) % 2][0], dp[(i-1) % 2][1] - prices[i])
- dp[i % 2][1] = max(dp[(i-1) % 2][1], dp[(i-1) % 2][0] + prices[i])
- return dp[(length-1) % 2][1]
相干题目：Leetcode123
文档讲解：Leetcode123
视频讲解：Leetcode123
1. Leetcode123.买卖股票的最佳机遇III
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的代价。计划一个算法来盘算你所能获取的最大利润。你最多可以完成 两笔 生意业务。
注意：你不能同时参与多笔生意业务（你必须在再次购买前出售掉之前的股票）。
提示：
- 1 <= prices.length <= 105
- 0 <= prices <= 105
- 思绪：
- 动规五部曲：
- 确定 dp 数组以及下标的寄义：一天一共有五个状态：
- 没有利用 （实在我们也可以不设置这个状态）
- 第一次持有股票
- 第一次不持有股票
- 第二次持有股票
- 第二次不持有股票
dp[j] 中 i 表现第 i 天，j 为 [0 - 4] 分别表现五个状态，dp[j] 表现第 i 天状态 j 所剩最大现金。（注意：dp[1] 表现的是第 i 天买入股票的状态，并不是说一定要第 i 天买入股票，有可能第 i-1 天 就买入了）
- 确定递推公式：
- 达到 dp[1] 状态，有两种详细利用：
- 利用一：第 i 天买入股票了，那么 dp[1] = dp[i-1][0] - prices；
- 利用二：第 i 天没有利用，而是沿用前一天买入的状态，即：dp[1] = dp[i - 1][1]；
那么 dp[1] 一定是选最大的，所以 dp[1] = max(dp[i-1][0] - prices, dp[i - 1][1])。
- 同理达到 dp[2] 状态也有两种利用：
- 利用一：第 i 天卖出股票了，那么 dp[2] = dp[i - 1][1] + prices；
- 利用二：第 i 天没有利用，沿用前一天卖出股票的状态，即：dp[2] = dp[i - 1][2]；
所以 dp[2] = max(dp[i - 1][1] + prices, dp[i - 1][2])。同理可推出剩下状态部分：
- dp[3] = max(dp[i - 1][3], dp[i - 1][2] - prices)；
- dp[4] = max(dp[i - 1][4], dp[i - 1][3] + prices)。
- dp 数组怎样初始化：
- 第 0 天没有利用就是 0，即：dp[0][0] = 0；
- 第 0 天做第一次买入的利用，dp[0][1] = -prices[0]；
- 第 0 天做第一次卖出相称于当天买入，当天卖出，所以 dp[0][2] = 0；
- 第 0 天第二次买入相称于第 0 天第一次买入后第一次卖出了，然后再买入一次（第二次买入），那么如今手头上没有现金，只要买入，现金就做相应的淘汰。所以初始化为：dp[0][3] = -prices[0]；
- 同理第 0 天第二次卖出初始化 dp[0][4] = 0。
- 确定遍历次序：从递归公式可以看出一定是从前向后遍历，由于 dp 依赖 dp[i - 1] 的数值。
- 举例推导 dp 数组：以输入 [1,2,3,4,5] 为例，dp 数组为：
- 动态规划
- ###版本一：
- 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]
|
