Best Time to Buy and Sell Stock III

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 two transactions.

f[k][ii]表示截止到ii步，用了k次transctions能够获得的最大利益

f[k][ii] = max(f[k][ii - 1], p[ii] - p[jj] + f[k - 1][hh])  ，其中 0<=jj<=ii - 1;
         = max(f[k, ii-1], prices[ii] + max(f[k-1, jj] - prices[jj]))

f[0][ii] = 0;
f[k][0] = 0;

根据上面的表达式，写出下面的式子，会超时

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size() <= 1)  return 0;

        int trans = 2;
        int n = prices.size();
        vector<vector<int>> dp(trans + 1, vector<int>(prices.size(), 0));

        for(int kk = 1; kk <= trans; kk++){

            for(int i = 1; i < prices.size(); i++){
                for(int j = i - 1; j >= 0; j--){
                    //dp[kk][i] = max(dp[kk][i - 1],prices[i] - prices[j] + dp[kk - 1][j])
                    dp[kk][i] = max(dp[kk][i],max(dp[kk][i - 1],prices[i] - prices[j] + dp[kk - 1][j]));
                }
            }
        }
        return dp[2][n - 1];

    }
};

int maxProfit(vector<int>& prices) {
        if (prices.size() <= 1)     
            return 0;
        else {
            int K = 2; // number of max transation allowed
            int maxProf = 0;
            vector<vector<int>> f(K+1, vector<int>(prices.size(), 0));
            for (int kk = 1; kk <= K; kk++) {
                int tmpMax = f[kk-1][0] - prices[0];
                for (int ii = 1; ii < prices.size(); ii++) {
                    f[kk][ii] = max(f[kk][ii-1], prices[ii] + tmpMax);
                    tmpMax = max(tmpMax, f[kk-1][ii] - prices[ii]);
                    maxProf = max(f[kk][ii], maxProf);
                }
            }
            return maxProf;
        }
    }

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size() <= 1)  return 0;

        int trans = 2;
        int n = prices.size();
        vector<vector<int>> dp(trans + 1, vector<int>(prices.size(), 0));

        for(int kk = 1; kk <= trans; kk++){
            int tmpMax = dp[kk - 1][0] - prices[0];
            for(int i = 1; i < prices.size(); i++){
                dp[kk][i] = max(dp[kk][i - 1],prices[i]+tmpMax);
                tmpMax = max(tmpMax,dp[kk - 1][i] - prices[i]);
            }
        }
        return dp[2][n - 1];

    }
};