leetcode: best time Best Time to Buy and Sell Stock 系列解题思路

这阵子一直在刷题，刷到这个系列了，写点自己能理解的心得体会吧，不是最优的，但个人认为理解的不太难。
言归征战，这个系列的大体思路就是给你一连串的股票价格，再加上各个限定条件，让你求出每种限制条件下，各自能获得最大的利润。(要是能有这个预知未来的能力，可以不用搬砖了，orz...)
I. 限制条件：只允许交易一次；
思路：先算出每次交易的利润，正表示盈余，负表示亏损，问题就转换为累加数组，求连续子数组的最大值，代码如下：

int maxProfiti(vector<int>& prices){
    int len = prices.size(), res = 0, i;
    if(len < 2) return 0;
    vector<int> profit(len, 0);
    for(i = 0; i < len-1; i++)
        profit[i] = prices[i+1]-prices[i];
    for(i=len-2; i >=0; i--){
        if(profit[i+1]>0)
            profit[i] += profit[i+1];
        res = res > profit[i] ? res: profit[i];
    }
    return res;
}

II.限制条件：允许进行尽可能多的交易；
思路：同上，求得利润数组，然后遍历，正数就加，负数就过，代码如下：

int maxProfitii(vector<int>& prices){
    int len = prices.size(), res = 0, i;
    if(len < 2) return 0;
    vector<int> profit(len, 0);
    for(i = 0; i < len-1; i++)
        profit[i] = prices[i+1]-prices[i];
    for( i = 0; i < len; i++){
        if(profit[i] > 0)
            res += profit[i];
    }
    return res;
}

III. 限制条件，最多允许交易两次；
思路：本来见到这题，想用上边题I的解题思路，dp[i][j]表示从i到j（包含）只允许一次交易的最大利润，但是时间复杂度太高，看了后面讨论区，恍然大悟，dp[k][i]表示到价格i为止，允许最多k次交易时的最大利润，则递推公式为dp[k][i]=max(dp[k][i-1], prices[i]-prices[j]+dp[k-1][j])，j的范围为[0, i]，代码如下：

int maxProfitiii(vector<int>& prices){
    int len = prices.size(), K = 2, temp, k, i;
    if(len < 2) return 0;
    vector<vector<int>> dp(K+1, vector<int>(len, 0));
    for(k = 1; k <= K; k++){
        temp = dp[k-1][0] - prices[0];
        for(i = 1; i < len; i++){
            dp[k][i] = max(dp[k][i-1], prices[i] +temp);
            temp = max(temp, dp[k-1][i]-prices[i]);
        }
    }
    return dp[K][len-1];
}

在代码里面耍了一个trick，除去了遍历dp[k-1][0]到dp[k-1][i]这一增加时间的代码块:)；
IV.限制条件：最多进行k次交易；
思路：有了三题的经验，第四题就手到擒来了，但是要注意k与所给数组长度的比较，因为如果2*k>=len 的话，就转换为题目II了，代码如下：

int maxProfitiv(int k, vector<int>& prices){
    int len = prices.size(), K , temp, i, res= 0;
    if(len < 2) return 0;
    if(len<=2*k){
            for(i = 1; i < len; i++)
                if(prices[i]>prices[i-1])
                    res +=(prices[i]-prices[i-1]);
            return res;
        }
    vector<int> dp(len, 0);
    for(K = 1; K <= k; K++){
        temp = dp[0] - prices[0];
        for(i = 1; i < len; i++){
            temp = max(temp, dp[i]-prices[i]);
            dp[i] = max(dp[i-1], prices[i] +temp);
        }
    }
    return dp[len-1];
}

V.限制条件：每次交易有交易费用fee，允许尽可能多的交易；
思路：刚开始以为顺着第四题思路,将第15行，改为dp[i] = max(dp[i-1], prices[i] +temp-fee);即可，但是超时了...继续讨论区，看大神--->建两个数组hold[i], sold[i]，表示到第i天，手中握有股票的最大利润和将第i天的股票卖出的最大利润，递推如下：

hold[i] = max(hold[i-1], sold[i-1]-prices[i]);

sold[i] = max(sold[i-1], hold[i-1]+prices[i]-fee);

代码如下：

int maxProfitiv( vector<int>& prices, int fee){
    int len = prices.size(), i;
    vector<int> hold(len, 0), sold(len, 0);
    hold[0] = -prices[0];
    for(i = 1; i < len; i++){
        hold[i] = max(hold[i-1], sold[i-1]-prices[i]);
        sold[i] = max(sold[i-1], hold[i-1]+prices[i]-fee);
    }
    return sold[len-1];
}

VI.限制条件：每次卖出后，必须冷静一天；
思路：哎，不知道为啥还得休整一天，顺着V题思路（没错，又是顺着思路。。。），hold[i]只与sold[i-2]有关系，代码修改如下：

int maxProfitvi(vector<int>& prices){
    int len = prices.size(), i;
    if(len < 2) return 0;
    vector<int> hold(len, 0), sold(len, 0);
    hold[0] = -prices[0];
    hold[1] = max(hold[0], -prices[1]);
    sold[1] = max(sold[0], hold[1]+prices[1]);
    for(i = 2; i < len; i++){
        hold[i] = max(hold[i-1], sold[i-2]-prices[i]);
        sold[i] = max(sold[i-1], hold[i-1]+prices[i]);
    }
    return sold[len-1];
}

总结：有些题目条件变化不大，可以顺着思路继续走，但是一旦问题发生的变化使得你之前的解题思路的总体假设不再成立，必须考虑换思路了。。。哎，路漫漫其修远兮，吾将上下而求索~~~继续努力！！！