LeetCode 123 Best Time to Buy and Sell Stock III

    
        标签：
        
            股票问题
        
            LeetCode
        
    发布于：2022-02-04 18:04:43
    编辑于：2022-02-05 16:52:55
    浏览量：948

题目分析

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/

这一次我们最多执行两次交易。

动态规划法

分析：

状态：天数，已交易次数，股票的持有状态；
动作：买入，卖出，不动；
base case：第 0 天时不能持有，且此时利润为 0；

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        vector<vector<vector<int>>> dp(prices.size() + 1, vector<vector<int>>(3, vector<int>(2, 0)));
        for (int i = 0; i <= 2; i++) {
            dp[0][i][1] = INT_MIN;
        }
        for (int d = 1; d <= prices.size(); d++) {
            for (int t = 1; t <= 2; t++) {
                dp[d][t][0] = max(dp[d-1][t][0], dp[d-1][t][1] + prices[d - 1]);
                dp[d][t][1] = max(dp[d-1][t][1], dp[d-1][t-1][0] - prices[d - 1]);
            }
        }
        int ans = 0;
        for (int i = 0; i <= 2; i++) {
            ans = max(ans, dp[prices.size()][i][0]);
        }
        return ans;
    }
};

暴力遍历法

我们只能交易两次，因此必然有个分解线，遍历该分界线，我们就将问题转化为执行一次或 0 次交易所能得到的最大利润。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int ans = 0;
        for (int i = 1; i <= int(prices.size()) - 2; i++) {
            ans = max(ans, helper(prices, 0, i) + helper(prices, i, prices.size() - 1));
        }
        ans = max(ans, helper(prices, 0, prices.size() - 1));
        return ans;
    }
    
    int helper(vector<int>& prices, int l, int r) {
        int profit = 0;
        int buy = prices[l];
        for (int i = l + 1; i <= r; i++) {
            if (prices[i] > buy) {
                profit = max(profit, prices[i] - buy);
            } else if (prices[i] < buy) {
                buy = prices[i];
            }
        }
        return profit;
    }
};

上面的实现中注意两点：

首先是 size() 给出的值是无符号类型，如果不加 int 的话，将溢出导致错误。如果不做处理，为当输入数组中只有一个元素时循环体将运行，造成 heap buffer overflow 。
其次，我们需要进行一次无分界线的利润寻找，case 为当输入为 [1, 5] 时，分界线将导致两次分开的投资的最大利润都为 0。

暴力遍历法（加入缓存）

上面的实现会 TLE，加入 cache 后：

class Solution {
public:
    vector<vector<int>> cache;
    int maxProfit(vector<int>& prices) {
        vector<vector<int>> cache(prices.size(), vector<int>(prices.size(), -1));
        this->cache = cache;
        int ans = 0;
        for (int i = 1; i <= int(prices.size()) - 2; i++) {
            ans = max(ans, helper(prices, 0, i) + helper(prices, i, prices.size() - 1));
        }
        ans = max(ans, helper(prices, 0, prices.size() - 1));
        return ans;
    }
    
    int helper(vector<int>& prices, int l, int r) {
        if (cache[l][r] != -1) return cache[l][r];
        int profit = 0;
        int buy = prices[l];
        for (int i = l + 1; i <= r; i++) {
            if (prices[i] > buy) {
                profit = max(profit, prices[i] - buy);
            } else if (prices[i] < buy) {
                buy = prices[i];
            }
        }
        cache[l][r] = profit;
        return profit;
    }
};

暴力遍历法（加入空间优化后的缓存）

上面的实现会 MLE（Memory Limit Exceeded），笑死第一次见。

实际上我们完全没有必要用一个二维矩阵来做 cache，两个向量，分别对应左边和右边的，下面的实现比较脏，就这样了：

class Solution {
public:
    vector<int> lcache;
    vector<int> rcache;
    int maxProfit(vector<int>& prices) {
        vector<int> lcache(prices.size(), -1);
        vector<int> rcache(prices.size(), -1);
        this->lcache = lcache;
        this->rcache = rcache;
        int ans = 0;
        for (int i = 1; i <= int(prices.size()) - 2; i++) {
            ans = max(ans, helper(prices, 0, i) + helper(prices, i, prices.size() - 1));
        }
        ans = max(ans, helper(prices, 0, prices.size() - 1));
        return ans;
    }
    
    int helper(vector<int>& prices, int l, int r) {
        if (l == 0 && r != prices.size() - 1) {
            if (lcache[r] != -1) return lcache[r];
        }
        if (l != 0 && r == prices.size() - 1) {
            if (rcache[l] != -1) return rcache[l];
        }
        
        int profit = 0;
        int buy = prices[l];
        for (int i = l + 1; i <= r; i++) {
            if (prices[i] > buy) {
                profit = max(profit, prices[i] - buy);
            } else if (prices[i] < buy) {
                buy = prices[i];
            }
        }
        
        if (l == 0 && r != prices.size() - 1) {
            if (lcache[r] != -1) lcache[r] = profit;
        }
        if (l != 0 && r == prices.size() - 1) {
            if (rcache[l] != -1) rcache[l] = profit;
        }
        return profit;
    }
};

笑死，又 TLE 了。

仔细想一下，这里的 cache 根本没有用啊，算了不删了，就这样吧。

Links: leetcode-123-best-time-to-buy-and-sell-stock-iii