LintCode 151. Best Time to Buy and Sell Stock III

class Solution {
public:
    /**
     * @param prices: Given an integer array
     * @return: Maximum profit
     */
    int maxProfit(vector<int> &prices) {
        // write your code here
        // 状态：f[n][k]: f[i][j]前i个元素交易最多j次的最大收益
        // 站在元素i向前看。几种情况：
        //1, 第i天有交易卖.分两种情况：1）第i-1天卖了 f[i][j] = p[i - 1][j] + diff（这一点很难想到要+diff。可以这么理解f[i][j]是如果做相应的动作的最大收益） 2）第i-1天没有卖。f[i][j] = f[i-1][j-1] + *. *又分为当天买卖和i-1天买 i天卖两种情况 *= max(0, diff)
        //2, 第i天没有交易 f[i][j] = f[i-1][j]
        // 状态P表示第i天卖了条件下最大交易j次的收益：P[i][j] = max(f[i - 1][j-1] + *, P[i - 1][j] + diff) (注意，其实P[i][j]就是上面分析中第一种情况)
        // initial P[0][j]= 0.....
        //结果f[n][k]
        int n = prices.size();
        if(n <= 1){
            return 0;
        }
        vector<vector<int>> f(n + 1, vector<int>(3, 0));
        vector<vector<int>> p(n + 1, vector<int>(3, 0));
        int diff = 0;
        for(int i = 1; i < n + 1; i++){
            for(int j = 1; j < 3; j++){
                if(i > 1){
                   diff = prices[i - 1] - prices[i - 2];
                }
                p[i][j] = max(f[i - 1][j - 1] + max(0, diff), p[i - 1][j] + diff);
                f[i][j] = max(f[i - 1][j], p[i][j]);
            }
        }
        return f[n][2];
     
    }
};

和43. Maximum Subarray III 一样的思路。根据某个点的所有可能动作分析出来需要两个状态来完成状态转移方程

二刷 2019年03月31日21:19:04
需要两个状态的 DP题目，需要研究。根据实际问题分析出 需要两个状态，一般是一个状态不能解决状态转移时所有的情况。
int maxProfit(vector<int> &prices) { // write your code here // DP //好吧，还是要整理DP思路先。 //状态 f[i][j] 前i-th element 最多交易j次的收益。 //转移：在第i-th 元素看，分情况： //1, day i 没有交易: f[i][j] = f[i - 1][j]. //2, day i 有交易。1) 第i - 1天没有卖: f[i][j] = f[i - 1][j - 1] + max(0, prices[i- 1] - prices[i - 2); // 2) 第i - 1天卖了: f[i][j] = p[i - 1][j] + diff; //需要第二个状态: 表示在第i天卖了这个特定条件下，最多交易j次的收益p[i][j],实际上就是上面f[i][j]里的case2. // 站在第i天，第i天卖了：p[i][j] = max(f[i - 1][j - 1] + max(0, prices[i - 1] - prices[i - 2]), p[i-1][j] + diff; //iniial, 都是0. const int n = prices.size(); if(n == 0){ return 0; } vector<vector<int>> f(n + 1, vector<int>(3, 0)); vector<vector<int>> p(n + 1, vector<int>(3, 0)); for(int i = 2; i < n + 1; i++){ for(int j = 1; j < 3; j++){ int diff = prices[i - 1] - prices[i - 2]; p[i][j] = max(f[i - 1][j - 1] + max(0, diff), p[i - 1][j] + diff); f[i][j] = max(p[i][j], f[i - 1][j]); } } return f[n][2]; }