股票问题总结"/>
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
更多推荐
LEETCODE力扣股票问题总结
发布评论