赞
踩
有一类动态规划的问题是给定一个股票价格序列,然后计算买卖股票所能获得的最大收益,这类问题通常有很多变种,例如只允许交易一次,允许交易多次或者增收交易税等。即问题的最大收益通常由交易的时间和允许的最大交易次数(每次交易指一次买与一次卖的一个组合)决定的。
可以用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
其中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]
由于收益最多的时候最后一步应该是将股票卖出,即最后返回的应该为T[i][k][0]
Best Time to Buy and Sell Stock
这道题目是求只允许一次交易的情况下所能获得的最大收益,即k=1的情况,其解法如下:
class Solution {
public:
int maxProfit(vector<int>& prices) {
int
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。