DP

常见的动态规划问题：

很多都是数列，在看到问题的时候，想着能不能在后面加一层数据，如果加的数据之后，结果和现在的结果不同，并且有相关性，考虑用动态规划

123 买卖股票

dp[i][j] 类型的,和普通的dp[i]一样，只不过多循环了几遍，在思考思路的时候，和普通的一样，先寻找递推公式，只不过需要多重复几遍，在实现代码的时候，在最外层多加上一层 for 循环。

DP[i][j] = max(DP[i][j - 1], prices[j] - prices[k] + DP[i - 1][k - 1](k = 0: j - 1))

public int maxProfit(int[] prices) {
    // corner case
    if(prices == null || prices.length == 0) return 0;
    
    int m = 2;
    int n = prices.length; 
    int[][] DP = new int[m + 1][n];
    for(int i = 0; i < m + 1; i++){
        for(int j = 0; j < n; j++){
            if(i == 0 || j == 0) DP[i][j] = 0;
            else{
                for(int k = 0; k < j; k++){
                    int prev = k == 0 ? 0: DP[i - 1][k - 1];
                    DP[i][j] = Math.max(DP[i][j - 1], prev + prices[j] - prices[k]);
                }
            }
        }   
    }	
        
    return DP[m][n - 1];	
}

优化一下：

int maxProfit(vector<int> &prices) {
        // f[k, ii] represents the max profit up until prices[ii] (Note: NOT ending with prices[ii]) using at most k transactions. 
        // f[k, ii] = max(f[k, ii-1], prices[ii] - prices[jj] + f[k-1, jj]) { jj in range of [0, ii-1] }这里f[k-1,jj]=f[k-1,jj-1],1、jj数据不用卖时相等。2、jj数据需要卖时，因为在这种条件下，jj需要买，因此同一天又买又卖，相当于也相等（这些人怎么想出来的）。用jj是因为要优化，
        //          = max(f[k, ii-1], prices[ii] + max(f[k-1, jj] - prices[jj]))
        // f[0, ii] = 0; 0 times transation makes 0 profit
        // f[k, 0] = 0; if there is only one price data point you can't make any money no matter how many times you can trade
        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;
        }
    }

讨论区最精简的写法：

    public int maxProfit(int[] prices) {
        int hold1 = Integer.MIN_VALUE, hold2 = Integer.MIN_VALUE;
        int release1 = 0, release2 = 0;
        for(int i:prices){                              // Assume we only have 0 money at first
            release2 = Math.max(release2, hold2+i);     // The maximum if we've just sold 2nd stock so far.
            hold2    = Math.max(hold2,    release1-i);  // The maximum if we've just buy  2nd stock so far.
            release1 = Math.max(release1, hold1+i);     // The maximum if we've just sold 1nd stock so far.
            hold1    = Math.max(hold1,    -i);          // The maximum if we've just buy  1st stock so far. 
        }
        return release2; ///Since release1 is initiated as 0, so release2 will always higher than release1.
    }
//很难理解，调换顺序
		int sell1 = 0, sell2 = 0, buy1 = Integer.MIN_VALUE, buy2 = Integer.MIN_VALUE;
		for (int i = 0; i < prices.length; i++) {
			buy1 = Math.max(buy1, -prices[i]);
			sell1 = Math.max(sell1, buy1 + prices[i]);
			buy2 = Math.max(buy2, sell1 - prices[i]);
			sell2 = Math.max(sell2, buy2 + prices[i]);
		}
		return sell2;

理解:

斐波那契数列

爬楼梯，摆砖块

d[i]=d[i-1]+d[i-2]