（leetcode算法题）​122. 买卖股票的最佳时机 II​ 和 123. 买卖股票的最佳时机 III

这两个题都可以进行转化，转换成等价问题求解

对于122的等价转换

求出所有能够赚钱的区间，这些区间满足一下特点

        1. 首尾相接，

        2. 区间末尾的值大于区间开头的值

        3. 每个区间尽可能的小

新的问题只要用贪心的思想就能求得问题的解

只要求出上述所有区间的首尾差之后求和，就能得到题目要求的结果

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int ret = 0;
        for (int i = 1; i < prices.size(); i++){
            if (prices[i] > prices[i - 1]){
                ret += prices[i] - prices[i - 1];
            }
        }
        return ret; 
    }
};

对于123的等价转换 

求出第 i 天结束之后是持有股票状态，而且已经进行了 k 次交易的最大利润 k = 0, 1, 2

求出k 取 0, 1, 2这三个值对应的利润的最大值，就是第 i 天结束之后能够获得的最大利润

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        // f 是第i天结束之后处于持有股票的状态，而且完成了j次交易获得的最大利润
        vector<vector<int>> f(n, vector<int>(3, -1 * 0x3fffff));
        auto g = f;
        f[0][0] = -1 * prices[0];
        g[0][0] = 0;
        int ret = 0;

        for(int i = 1; i < n; ++i){
            for(int j = 0; j < 3; ++j){
                f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);
                g[i][j] = g[i - 1][j];
                if(j - 1 >= 0){
                    g[i][j] = max(g[i - 1][j], f[i - 1][j - 1] + prices[i]);
                }
                ret = max(ret, g[i][j]);
            }
        }
        return ret;
    }
};