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

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

可以用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]

LeetCode里面相关的经典题目

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

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int T_i10=0,T_i11=INT_MIN;
        for(int price:prices){
            T_i10=max(T_i10,T_i11+price);
            T_i11=max(T_i11,-price);
        }
        return T_i10;
    }
};

Best Time to Buy and Sell Stock II 这道题目是不限制交易次数的情况，即k=Infinity的时候，此时k-1=k，那么状态转移方程可以写成如下形式：

T[i][k][0] = max(T[i-1][k][0], 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]) = max(T[i-1][k][1], T[i-1][k][0] - prices[i])

因为T[i][k][0]在前一步进行了更新，那么可以利用一个临时变量来保存T[i][k][0]，其代码如下：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int T_ik0=0,T_ik1=INT_MIN;
        for(int price:prices){
            int T_ik0_old=T_ik0;
            T_ik0=max(T_ik0,T_ik1+price);
            T_ik1=max(T_ik1,T_ik0_old-price);
        }
        return T_ik0;
    }
};

Best Time to Buy and Sell Stock III 这道题目是找在限制最大交易次数为2的情况下所能获得的最大收益，此时k=2或k=1，与k=1的情况类似，其状态转移方程可以写成以下形式：

T[i][2][0] = max(T[i-1][2][0], T[i-1][2][1] + prices[i])
T[i][2][1] = max(T[i-1][2][1], T[i-1][1][0] - prices[i])
T[i][1][0] = max(T[i-1][1][0], T[i-1][1][1] + prices[i])
T[i][1][1] = max(T[i-1][1][1], -prices[i])

最后返回的最优解即为T[i][k][0]=T[i][2][0]，完整解法如下：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int T_i10=0,T_i11=INT_MIN;
        int T_i20=0,T_i21=INT_MIN;
        for(int price:prices){
            T_i20=max(T_i20,T_i21+price);
            T_i21=max(T_i21,T_i10-price);
            T_i10=max(T_i10,T_i11+price);
            T_i11=max(T_i11,-price);
        }
        return T_i20;
    }
};

Best Time to Buy and Sell Stock IV 这道题目是将k作为参数传入求解函数里面，可以看出来每一次能够获得收益的交易都是需要两天时间的，那么当k>=n/2的时候再增加k也不会增加收益，那么此时可以看作是k=Infinity，这种情况与前面的问题相同。当k < n/2的时候则跟k=2的情况类似，可以通过创建数组的方式来向前更新。解法如下：

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        if(k>=prices.size()>>1){
            int T_ik0=0,T_ik1=INT_MIN;
            for(int price:prices){
                int T_ik0_old=T_ik0;
                T_ik0=max(T_ik0,T_ik1+price);
                T_ik1=max(T_ik1,T_ik0_old-price);
            }
            return T_ik0;
        }
        vector<int> T_ik0(k+1,0);
        vector<int> T_ik1(k+1,INT_MIN);
        for(int price:prices){
            for(int j=k;j>0;j--){
                T_ik0[j]=max(T_ik0[j],T_ik1[j]+price);
                T_ik1[j]=max(T_ik1[j],T_ik0[j-1]-price);
            }
        }
        return T_ik0[k];
    }
};

Best Time to Buy and Sell Stock with Cooldown 这道题目并没有限制k的取值，即为Infinity，但是有另外一个限制就是不能在前一天卖掉股票然后第二天又马上买入，起到一个cooldown的作用。那么在这个状态转移方程中，对于T[i][k][1]的更新会有所不同，在第i天采取休息的情况下是相同的，在采取买入的操作的时候更新为T[i-2][k-1][0]=T[i-2][k][0]，其状态转移方程如下：

T[i][k][0] = max(T[i-1][k][0], T[i-1][k][1] + prices[i])
T[i][k][1] = max(T[i-1][k][1], T[i-2][k][0] - prices[i])

该题目的代码为：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int T_ik0_pre=0,T_ik0=0,T_ik1=INT_MIN;
        for(int price:prices){
            int T_ik0_old=T_ik0;
            T_ik0=max(T_ik0,T_ik1+price);
            T_ik1=max(T_ik1,T_ik0_pre-price);
            T_ik0_pre=T_ik0_old;
        }
        return T_ik0;
    }
};

Best Time to Buy and Sell Stock with Transaction Fee 这道题目与之前的不同在于，每次交易都要增收一定额度的交易税，而同样也是不限制交易次数的，这个可以在每次交易的时候（卖或者买的时候都可以）减去交易税的金额，然后再更新相应的最大收益T[i][k][0]或者T[i][k][1]，其状态转移方程如下：

T[i][k][0] = max(T[i-1][k][0], T[i-1][k][1] + prices[i])
T[i][k][1] = max(T[i-1][k][1], T[i-1][k][0] - prices[i] - fee)

or

T[i][k][0] = max(T[i-1][k][0], T[i-1][k][1] + prices[i] - fee)
T[i][k][1] = max(T[i-1][k][1], T[i-1][k][0] - prices[i])

算法代码如下：

#include<climits>
class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        long T_ik0=0,T_ik1=LONG_MIN;
        for(int price:prices){
            long T_ik0_old=T_ik0;
            T_ik0=max(T_ik0,T_ik1+price);
            T_ik1=max(T_ik1,T_ik0_old-price-fee);
        }
        return (int)T_ik0;
    }
};

参考文章：https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/discuss/108870/Most-consistent-ways-of-dealing-with-the-series-of-stock-problems

#代码 & 数学