Best Time to Buy and Sell Stock IV

另一种动态规划解法：(参考 here，here)

buy[i][j]：第i天处于买入股票状态，同时从开始到今天可最多进行j次交易时的最大利润
sold[i][j]：第i天处于卖出股票状态，同时从开始到今天可最多进行j次交易时的最大利润

对于buy[i][j]，它的更新有两种情况：
一种是第i天没有买入股票，则buy[i][j]=buy[i-1][j]
一种是第i天买入股票，buy[i][j]=sold[i-1][j-1]-prices[i]

因此，
buy[i][j]=max(buy[i-1][j], sold[i-1][j-1]-prices[i])

对于sold[i][j]，它的更新有两种情况：
一种是第i天没有卖出股票，则sold[i][j]=sold[i-1][j]
一种是第i天有卖出股票，sold[i][j]=buy[i-1][j]+prices[i]

因此，
sold[i][j]=max(sold[i-1][j], buy[i-1][j]+prices[i])

因此总的状态方程为：
buy[i][j]=max(buy[i-1][j], sold[i-1][j-1]-prices[i])
sold[i][j]=max(sold[i-1][j], buy[i-1][j]+prices[i])

发现什么问题了没有？

第 i 天的结果只与第 i - 1 天的结果有关，与 i - 1 之前的天数完全无关！

既然如此，更新只需要用到前一天的数据，可以考虑转为一维dp：

buy[j]=max(buy[j], sold[j-1]-prices[i])
sold[j]=max(sold[j], buy[j]+prices[i])


注意注意，前方高能！
我们看到第 i 天的buy[j]需要用到前一天的sold[j-1]，但是如果我们从j=0开始遍历的话，此时得到的sell[j-1]已经变成了第 i 天的sold[j-1]了啊。

解决方法
从j=k开始遍历到1，那么修改buy[j]和sold[j]之时，就能保证sold[j-1]还是前一天的值
---------------------

同是在计算sold[j]时，我们需要用到buy[i-1][j]，但是转为一维dp后，因为我们先计算了buy[j]，所以此时的 buy[j] 实际上是 buy[i][j]，这样就与我们需要的不符。

解决办法：在更新buy[j]前，把它的值先保存到一个临时变量中。
但是在测试中发现，不用这样做，也不影响结果。原因分析如下
1）如果buy[i][j]==buy[i-1][j]，则这样当然不会影响结果。
2）如果buy[i][j]==sold[i-1][j-1]-prices[i]，这意味着
sold[i-1][j-1]-prices[i]>=buy[i-1][j]
<=>  sold[i-1][j-1]>=buy[i-1][j]+prices[i]   (*)
又因为
sold[i][j]=max(sold[i-1][j], buy[i-1][j]+prices[i])，
 那么，如果用 buy[i][j]来代替 buy[i-1][j]计算，buy[i-1][j]+prices[i]=sold[i-1][j-1]-prices[i]+prices[i]=sold[i-1][j-1]，
显然 sold[i-1][j]>=sold[i-1][j-1]
根据(*), sold[i-1][j-1]>=buy[i-1][j]+prices[i]
这就是说，不论 buy[j] 值正确与否，sold[i][j]总是等于sold[i-1][j]，故也不会影响结果。


另外一种方法是把sold在buy前面计算：
总的状态方程为：
sold[i][j]=max(sold[i-1][j], buy[i-1][j]+prices[i])
buy[i][j]=max(buy[i-1][j], sold[i-1][j-1]-prices[i])

==》
sold[j]=max(sold[j], buy[j]+prices[i])
buy[j]=max(buy[j], sold[j-1]-prices[i])


    int maxProfit(int k, vector<int>& prices) {
        if(prices.size() ==0) return 0;
        int len = prices.size(), ans =0;
        if(k >= len/2)
        {
            for(int i = 1; i < len; i++)
                if((prices[i]-prices[i-1])>0) ans += prices[i]-prices[i-1];
            return ans;
        }
        vector<int> buy(len+1, INT_MIN), sold(len+1, 0);
        for(auto val: prices)
        {
            for(int j =k; j >0; j--)
            {
                int tmp =buy[j];
                buy[j] = max(sold[j-1]-val, buy[j]);
                sold[j] = max(tmp+val, sold[j]);
            }
        }
        return sold[k];
    }