LeetCode 123 Best Time to Buy and Sell Stock III

Tag: 股票问题 LeetCode Posted on 2022-02-04 18:04:43 Edited on 2022-02-05 16:52:55 Views: 169

题目分析

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

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

动态规划法

分析:

  1. 状态:天数,已交易次数,股票的持有状态;
  2. 动作:买入,卖出,不动;
  3. 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;
    }
};

上面的实现中注意两点:

  1. 首先是 size() 给出的值是无符号类型,如果不加 int 的话,将溢出导致错误。 如果不做处理,为当输入数组中只有一个元素时循环体将运行,造成 heap buffer overflow 。
  2. 其次,我们需要进行一次无分界线的利润寻找,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 根本没有用啊,算了不删了,就这样吧。

未经允许,禁止转载,本文源站链接:https://iamazing.cn/