【leetcode】122. 买卖股票的最佳时机2

题目内容

122. 买卖股票的最佳时机2

思路分析

本题是股票系列的第二题，似乎一共有五六道题，做完以后就可以去炒股发家致富了🤣。

本题共有三种思路，拟人（方法一）、动态规划（方法二和三）和贪心（方法四）。其中方法一感觉也可以叫贪心。

感觉拟人和贪心比较容易想到，而动态规划，特别是二维动态规划，思路从何而来？感觉需要看看《算法导论》之类的书学习下相关的理论知识了。

方法二三四的参考链接

方法一：拟人

模拟人的思考过程。假设当天比前一天价格低，则心里会想“我要是更早以前买入最低点，前一天卖出就好了”。这样就可以保证整个交易过程收益最大。

方法二：动态规划

你可以尽可能地完成更多的交易（多次买卖一支股票）。你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

审题后发现，由于以上规则的存在，因此每天共有两个状态：持仓（手里有股票）/空仓（手里没股票，只有现金）。每天共可以进行三种操作：买/卖/不动。而前一天持仓时只能卖/不动，前一天空仓时只能买/不动。

因此，设cur_cash[i][j]为每天交易完成后持有的现金，i为第i天（从0开始计），j为0代表当天交易完后空仓，j为1代表当天交易完持仓，则可以列出状态转移方程：

cur_cash[i][0] = max(cur_cash[i - 1][0], cur_cash[i - 1][1] + prices[i])
cur_cash[i][1] = max(cur_cash[i - 1][1], cur_cash[i - 1][0] - prices[i])

边界条件：

cur_cash[0][0] = 0
cur_cash[0][1] = -prices[0]

方法三：动态规划优化

方法二中的动态规划每天的状态只与前一天的状态有关，因此与121题题解对动态规划的优化相类似，只需要使用常数个变量记录前一天的状态，即可把空间复杂度由O(n)降为O(1)。

方法四：贪心

贪心算法的策略为只要每天的价格比前一天的价格低，就买入前一天的并卖出，这样就可以获得最大收益。其实质和方法一相似，只是方法一是一大段一大段贪，这里是一天一天的贪。

代码

#include <vector>
#include <limits>

using namespace std;

class Solution {
public:
    // 自己解法 拟人法
    // - 一直维护最低价格、前一天的价格和总利润
    // - 如果今天跌了，就意味着不再能卖出更高的价格，因此以昨天的价格卖出，
    // 并且更新最低价格为今天的价格
    // - 对于最后一天若没跌，则进行特殊处理，加上最后一天的利润
    // 时间复杂度O(n)，空间复杂度O(1)
    int maxProfit1(vector<int>& prices) {
        int n = prices.size();
        if (n == 0) return 0;
        
        int min_price{ prices[0] }, last_price{ prices[0] }, total_profit{ 0 };

        for (int i = 1; i < n; ++i) {
            // 最后一天且没跌
            if (i == n - 1 && prices[i] >= last_price) { //  这里需要取到等号，因为会有类似输入为[1,2,2]的情况
                total_profit += prices[i] - min_price;
            }
            // 今天跌了，则以昨天的价格卖出，并且更新最低价格为今天的价格
            else if (prices[i] < last_price) {
                total_profit += last_price - min_price;
                min_price = prices[i];
            }
            // 更新最低价格
            else if (prices[i] < min_price) {
                min_price = prices[i];
            }

            // 更新前一天的价格
            last_price = prices[i];
        }

        return total_profit;
    }

    // 动态规划
    // 每天有三种选择：买/卖/不动；有两种状态：持仓/空仓。
    // 由于不能同时参与多笔交易（必须在再次购买前出售掉之前的股票）
    // 因此，若某一天持仓，则其下一天只能卖/不动，对应的下一天状态为空仓/持仓
    // 若某一天空仓，则其下一天只能买/不动，对应的下一天状态为持仓/空仓
    // 然后即可根据某天的状态写状态转移方程
    // 时间复杂度O(n)，空间复杂度O(n)
    int maxProfit2(vector<int>& prices) {
        
        int n = prices.size();
        
        // 当前交易完后拥有的现金
        // 第一维的n表示第n天
        // 第二维的1/0表示当天最终手上有/无股票
        vector<vector<int>> cur_cash(n, vector<int>(2));  

        if (n == 0) return 0;

        cur_cash[0][0] = 0;
        cur_cash[0][1] = -prices[0];

        for (int i = 1; i < n; ++i) {
            cur_cash[i][0] = max(cur_cash[i - 1][0], cur_cash[i - 1][1] + prices[i]);  // 前一天空仓且不动/前一天持仓卖掉 -> 今天空仓
            cur_cash[i][1] = max(cur_cash[i - 1][1], cur_cash[i - 1][0] - prices[i]);  // 前一天持仓且不动/前一天空仓且买入 -> 今天持仓
        }

        return cur_cash[n - 1][0];  // 最后一天空仓才能现金最多
    }

    // 动态规划优化
    // 因为状态转移方程只参考前一天的，因此只需要记录前一天的两个状态
    // 时间复杂度O(n)，空间复杂度O(1)
    int maxProfit3(vector<int>& prices) {

        int n = prices.size();

        // 当前交易完后拥有的现金
        // 第一维的n表示第n天
        // 第二维的1/0表示当天最终手上有/无股票

        if (n == 0) return 0;

        int pre_cash_empty{ 0 }, pre_cash_hold{ -prices[0] }, cur_cash_empty{ 0 }, cur_cash_hold{ 0 };

        for (int i = 1; i < n; ++i) {
            cur_cash_empty = max(pre_cash_empty, pre_cash_hold + prices[i]);  // 前一天空仓且不动/前一天持仓卖掉 -> 空仓
            cur_cash_hold = max(pre_cash_hold, pre_cash_empty - prices[i]);  // 前一天持仓且不动/前一天空仓且买入 -> 持仓
            pre_cash_empty = cur_cash_empty;
            pre_cash_hold = cur_cash_hold;
        }

        return cur_cash_empty;  // 最后一天空仓才能现金最多
    }


    // 贪心，如果每天的价格比前一天的价格高，就卖出
    // 此方法与拟人法的区别是拟人是一大段一大段卖，而此方法是一天一天卖
    // 时间复杂度O(n)，空间复杂度O(1)
    int maxProfit(vector<int>& prices) {
        
        int n = prices.size();
        
        if (n == 0) return 0;

        int pre_price{ prices[0] };
        int total_profit{ 0 };

        for (int price : prices) {
            if (price > pre_price) total_profit += price - pre_price;
            pre_price = price;
        }

        return total_profit;
    }
};


int main() {
    Solution s;
    vector<int> input{ 1,2,3,4,5 };

    int output;
    output = s.maxProfit(input);

    return output;
}

收获

之前学的拟人法在这用上了，而且复杂度也很优秀
相当于做了一道最简单二维动态规划题目，并且像上一道题目一样对其进行了优化（不过我做的时候并没有想到，有点可惜）
再次加强了对贪心算法的掌握