題目來源
Say you have an array for which the ith 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).

這道題呢锭亏，大家肯定一看也知道應(yīng)該用DP剥纷，但是具體應(yīng)該怎么用呢郑现，肯定是個(gè)二維的DP拼坎。假設(shè)dp[k][i]表示前i天里交易k次最大盈利，那么dp[k][i]可以有兩種可能座舍，一種是在第i天的時(shí)候沒有交易則dp[k][i] = dp[k][i-1]扎拣，另一種是在第i天的時(shí)候有交易則dp[k][i] = dp[k-1][j-1] + price[i] - price[j]腌歉，j表示上一次買入的時(shí)候的那一天依痊。
那么dp[k][i] = max(dp[k][i-1], dp[k-1][j-1] + price[i] - price[j])避除。
dp[0][i] = 0 因?yàn)?次交易的話盈利肯定是0。
dp[k][0] = 0 因?yàn)榈?天肯定也沒有盈利抗悍。
代碼如下所示：

class Solution {
public:
   int maxProfit(int k, vector<int>& prices) {
       int n = prices.size();
       vector<vector<int>> dp(k+1, vector<int>(n+1, 0));
       for (int i=1; i<=k; i++) {
           for (int j=1; j<=n; j++) {
               int tmp = 0;
               for (int jj=1; jj<j; jj++)
                   tmp = max(tmp, dp[i-1][jj-1] + prices[j-1] - prices[jj-1]);
               dp[i][j] = max(dp[i][j-1], tmp);
           }
       }
       return dp[k][n];
   }
};

然后結(jié)果怎么樣，沒錯(cuò)钳枕，又是TLE缴渊！又超時(shí)了！時(shí)間復(fù)雜度有點(diǎn)高鱼炒，O(n^3)衔沼。
然后參考了下大神的，修改了一下代碼，改成O(n^2)的指蚁。

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        if (n < 2)
            return 0;
        int maxPro = 0;
        vector<vector<int>> dp(k+1, vector<int>(n+1, 0));
        for (int i=1; i<=k; i++) {
            int tmpMax = dp[i-1][1] - prices[0];
            for (int j=1; j<=n; j++) {
                dp[i][j] = max(dp[i][j-1], tmpMax + prices[j-1]);
                tmpMax = max(tmpMax, dp[i-1][j] - prices[j-1]);
                maxPro = max(maxPro, dp[i][j]);
            }
        }
        return maxPro;
    }
};

巧妙的引入了一個(gè)tmpMax來存儲(chǔ)以前dp[i-1][jj-1] + prices[j-1] - prices[jj-1]中的dp[i-1][jj-1] - prices[jj-1]菩佑。
但是還是A不了，當(dāng)k或者prices非常大的時(shí)候凝化，內(nèi)存溢出了稍坯。
繼續(xù)看看怎么改進(jìn)，可以采取一些小技巧來防止TLE或者溢出搓劫。
比如說假如交易次數(shù)達(dá)到天數(shù)的一半瞧哟，那么最大收益可以直接算出來，不用管交易次數(shù)的限制枪向。

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        if (n < 2)
            return 0;
        if (k > n / 2)
            return quickSolver(prices);
        int maxPro = 0;
        vector<vector<int>> dp(k+1, vector<int>(n+1, 0));
        for (int i=1; i<=k; i++) {
            int tmpMax = dp[i-1][1] - prices[0];
            for (int j=1; j<=n; j++) {
                dp[i][j] = max(dp[i][j-1], tmpMax + prices[j-1]);
                tmpMax = max(tmpMax, dp[i-1][j] - prices[j-1]);
                maxPro = max(maxPro, dp[i][j]);
            }
        }
        return maxPro;
    }
    
    int quickSolver(vector<int> prices)
    {
        int n = prices.size();
        int res = 0;
        for (int i=1; i<n; i++) {
            if (prices[i] > prices[i-1])
                res += prices[i] - prices[i-1];
        }
        return res;
    }
};