当前位置:   article > 正文

[LeetCode]动态规划中股票问题的通用解法_股票问题 动态规划

股票问题 动态规划

动态规划中股票问题的通用解法

有一类动态规划的问题是给定一个股票价格序列,然后计算买卖股票所能获得的最大收益,这类问题通常有很多变种,例如只允许交易一次,允许交易多次或者增收交易税等。即问题的最大收益通常由交易的时间和允许的最大交易次数(每次交易指一次买与一次卖的一个组合)决定的。

可以用T[i][k]表示在第i天结束的时候最多经过k次交易所能获得的最大收益,另外在第i天结束的时候可以有两种状态,手上有股票T[i][k][1]或者手上没有股票T[i][k][0],可以得到以下初始状态:

T[-1][k][0] = 0, T[-1][k][1] = -Infinity
T[i][0][0] = 0, T[i][0][1] = -Infinity
  • 1
  • 2

其中T[-1][k][0] = 0与T[i][0][0] = 0意味着在初始状态下(i=-1)即没有股票的时候收益为0,在最多允许0次交易的情况下收益也为0。而T[-1][k][1]=T[i][0][1] = -Infinity意味着在初始情况下手里有股票以及允许0次交易的情况下手里有股票是不可能的,将其收益设为-Infinity。

而对于状态的转移,我们可以得到以下的公式

T[i][k][0] = max(T[i-1][k][0], T[i-1][k][1] + prices[i])
//对于在第i天结束的时候手里没有股票的情况下,在这一天所能采取的操作有两种
//1.不进行交易,即最大收益为T[i-1][k][0]
//2.进行卖出,即第i天的最大收益为上一天有股票时的最大收益加上当天的卖价为T[i-1][k][1] + prices[i]
T[i][k][1] = max(T[i-1][k][1], T[i-1][k-1][0] - prices[i])
//在第i天结束手里有股票时,同样有两种操作:
//1.不进行交易,即为T[i-1][k][0]
//2.进行买入,这时的买入增加了一次交易次数,那么i-1天结束的最大交易次数为k-1,即当天结束的最大收益为T[i-1][k-1][0] - prices[i]
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

由于收益最多的时候最后一步应该是将股票卖出,即最后返回的应该为T[i][k][0]

LeetCode里面相关的经典题目

Best Time to Buy and Sell Stock
这道题目是求只允许一次交易的情况下所能获得的最大收益,即k=1的情况,其解法如下:

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int
  • 1
  • 2
  • 3
  • 4
声明:本文内容由网友自发贡献,转载请注明出处:【wpsshop】
推荐阅读
相关标签
  

闽ICP备14008679号