188. Best Time to Buy and Sell Stock IV !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

Q:
Say you have an array for which the i^th element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most k transactions.
Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

A:

思路：dp

设dp[t][d]为t次交易,新进d天的最大利润：

• 每次开始的时候，初始化为不用最新一天，或者少用一次transaction.    
•  DP[t][d] = max(DP[t-1][d], DP[t][d-1]);
• 状态转移方程:  DP[t][d] = max(DP[t][d], DP[t-1][j] + prices[d]- prices[j])
•  j in [0,day-1]  inclusive.
• 第一项为第i天不进行交易，第二项为枚举j 从0~i-1，第j天买入，第i天卖出

注意当k >= len(prices) / 2的时候，说明相当于无限次交易，和第122题Best Time to Buy and Sell Stock II 一样。

上面的复杂度为O(kn^2)代码如下:

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        if(n<=1)
            return 0;
        k = min(k, n/2); // in case given k is tooo big, 
        vector<vector<int>> DP(k+1, vector<int>(n,0));
        for(int t = 1; t < k+1; t++){// t -> transaction count
            for(int d =1; d < n; d ++){ // d --> day
                //if not use newly added value
                DP[t][d] = DP[t][d-1];
                for(int j = d-1; j>=0; j--){
                    DP[t][d] = max(DP[t][d], DP[t-1][j] + prices[d]- prices[j]);
                }
            }
        }
        return DP[k][n-1];
    }
};
然而上面的超时了。

仔细看，我们有3层循环。

然后，其实状态转移函数里。  

DP[t-1][j] + prices[d]- prices[j]  ==> (DP[t-1][j] - prices[j]) + price[d] 

而(DP[t-1][j] - prices[j]) 每次只需要记录一个最大就可以了。

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        if(n<=1)
            return 0;
        k = min(k, n/2); // in case given k is tooo big, 
        vector<vector<int>> DP(k+1, vector<int>(n,0));
        for(int t = 1; t < k+1; t++){// t -> transaction count
            int pre_max_diff = DP[t-1][0] - prices[0];
            for(int d =1; d < n; d ++){ // d --> day
                //if not use newly added value
                DP[t][d] = max(DP[t][d-1], pre_max_diff + prices[d]);
                pre_max_diff = max(pre_max_diff, DP[t-1][d] - prices[d] );
            }
        }
        return DP[k][n-1];
    }
};

Mistakes:

这里不能一行一行地计算DP， 要一列一列地计算。-------这个是我以前没有这样搞过的。
也就是说。 要慎重地考虑DP哪一个 变量