LEETCODE力扣股票问题总结
21 浏览量
2020-12-20
22:53:40
上传
评论
收藏 88KB PDF 举报
LEETCODE力扣股票问题总结力扣股票问题总结
在力扣网站中，最常见的动态规划问题就是股票系列的问题
这里我把题号给放上来
121
122
123
188
309
714
股票问题总思路股票问题总思路
既然涉及到动态规划，那么我们肯定是需要根据题意来定义状态转移方程的
对于股票的操作，我们一共有3个，分别是买，卖，不交易
我们可以定义一个三维的数组，维度分别代表天数，交易次数，状态（用0，1代表没持有股票还是持有股票）
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
这个方程意思是我现在没持有股票，那么有两种可能，一个是昨天我就没有持有股票，也就是dp[i-1][k][0]，第二个是我昨天持有股票，今天卖了，因此是
dp[i-1][k][1]加上卖出去股票的价格
同理我们可以写出另外一个
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
这个方程的意思是我现在持有股票，那么有两种可能，一个是昨天我就持有股票，对于的就是dp[i-1][k][1]。第二个是我昨天没
持有股票，今天买了。由于涉及到买，所以我们交易次数要减1，天数减1，同时减去今天买股票的钱
上面这两个方程很重要，这两个方程能解决股票系列所有问题
推导出转移方程，我们来看看基本情况
基本情况：
dp[-1][k][0] = 0
解释：因为 i 是从 0 开始的，所以 i = -1 意味着还没有开始，这时候的利润当然是 0 。
dp[-1][k][1] = -infinity
解释：还没开始的时候，是不可能持有股票的，用负无穷表示这种不可能。
dp[i][0][0] = 0
解释：因为 k 是从 1 开始的，所以 k = 0 意味着根本不允许交易，这时候利润当然是 0 。
dp[i][0][1] = -infinity
解释：不允许交易的情况下，是不可能持有股票的，用负无穷表示这种不可能
初探股票问题初探股票问题
121. 买卖股票的最佳时机
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
注意：你不能在买入股票前卖出股票。
示例 1:
输入: [7,1,5,3,6,4] 输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
这是股票系列的第一个问题，这题只有一次交易次数，所以我们可以把第二维度给去掉
然后应用我们的转移方程即可
def maxProfit(prices: List[int]) -> int:
n = len(prices)
dp = [[0, 0] for _ in range(n)] for i in range(n):
if i - 1 == -1:
dp[i][0] = 0
dp[i][1] = -prices[i]
continue
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])
dp[i][1] = max(dp[i - 1][1], -prices[i])
return dp[n - 1][0]
评论0