代码随想录算法训练营第四十九天|121. 买卖股票的最佳时机、122.买卖股票的最佳时机II

LeetCode 121. 买卖股票的最佳时机

链接：121. 买卖股票的最佳时机

思路：

这道题目用动规写起来效率其实是不如贪心的，但是对于解类似的题目还是有帮助，重点是理解动规的过程。首先定义下标：dp[i][0]表示第i天持有股票所能得到的最大金钱，dp[i][1]表示第i天不持有股票所能得到的最大金钱。所以dp是一个二维数组，大小为prices.size() x 2。然后初始化dp，dp[0][0]表示第一天买入股票，所以dp[0][0]初始化为-prices[0]，持有金额为负，因为这个时候是花钱买的股票。dp[0][1]还是0，这个时候既没有买入操作也没有卖出操作，所以是0。

然后从i=1开始遍历prices数组，确定递推公式：

dp[i][0] = max(dp[i-1][0], -prices[i])：第i天持有股票有两种情况：1、第i-1天就持有股票，所能持有的最大金额为前一天持有股票时的金额dp[i-1][0]。 2、第i天买入股票，所能持有的最大金额为当天股票的价格的负数-prices[i]，因为是花钱买了股票。
dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i])：第i天未持有股票有两种情况：1、第i-1天就未持有股票，所能持有最大金额为前一天未持有股票的金额dp[i-1][1]。 2、第i天卖出股票，所能持有最大金额为前一天持有股票的金额dp[i-1][0]，加上当天出售股票所获得的金额prices[i]。

最后返回最后一天出售股票时的金额dp[prices.size() - 1][1]，因为出售股票永远比持有股票时所持有的现金要多。

代码：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        // 定义下标：dp[i][0]表示第i天持有股票所能得到的最大金钱
        // dp[i][1]表示第i天不持有股票所能得到的最大金钱
        vector<vector<int>> dp(prices.size(), vector<int>(2));
        // 第0天持有股票相当于买入第0天的股票，持有金钱相当于-prices[0]
        dp[0][0] = -prices[0];
        for (int i = 1; i < prices.size(); i++)
        { 
            // 第i天持有股票有两种情况：1、第i-1天就持有股票 2、第i天买入股票
            dp[i][0] = max(dp[i-1][0], -prices[i]);
            // 第i天未持有股票有两种情况：1、第i-1天就未持有股票 2、第i天卖出股票
            dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i]);
        }
        return dp[prices.size()-1][1];
    }
};

但其实我们可以发现，在遍历的过程中我们只用了前一天的数值dp[i-1]，所以二维dp数组可以压缩成2x2大小，只记录当前天所持有的最大金额和前一天所持有的最大金额。

空间优化代码：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        // 定义下标：dp[i][0]表示第i天持有股票所能得到的最大金钱
        // dp[i][1]表示第i天不持有股票所能得到的最大金钱
        vector<vector<int>> dp(2, vector<int>(2));
        // 第0天持有股票相当于买入第0天的股票，持有金钱相当于-prices[0]
        dp[0][0] = -prices[0];
        for (int i = 1; i < prices.size(); i++)
        { 
            // 第i天持有股票有两种情况：1、第i-1天就持有股票 2、第i天买入股票
            dp[i % 2][0] = max(dp[(i - 1) % 2][0], -prices[i]);
            // 第i天未持有股票有两种情况：1、第i-1天就未持有股票 2、第i天卖出股票
            dp[i % 2][1] = max(dp[(i - 1) % 2][1], dp[(i - 1) % 2][0] + prices[i]);
        }
        return dp[(prices.size() - 1) % 2][1];
    }
};

LeetCode 122. 买卖股票的最佳时机 II

链接：122. 买卖股票的最佳时机 II

思路：

本题涉及到多次买卖，之前也用贪心法做过，贪心法的思路为计算所有的正收入，同样也可以用动态规划的做法做出来。dp下标定义和上一题一样，dp[i][0]表示第i天持有股票所能得到的最大金钱，dp[i][1]表示第i天不持有股票所能得到的最大金钱，初始化和遍历顺序也和上题是一致的。

不同的地方在于递推公式，因为可以多次买卖，本题中所能获得的最大金额是累计的，所以在买入股票的时候，所持金额不是直接变成股票的价格的负数，而是用当前所持金额减去股票价格。当前持有金额为前一天为持有股票时的金额dp[i-1][1]，所以在第i天买入股票所持有的最大金额为dp[(i - 1) % 2][1]-prices[i]（采用滚动数组）。最后完整递推公式如下：

持有股票时的递推公式为：dp[i % 2][0] = max(dp[(i - 1) % 2][0], dp[(i - 1) % 2][1]-prices[i])。
未持有股票时的递推公式为：dp[i % 2][1] = max(dp[(i - 1) % 2][1], dp[(i - 1) % 2][0] + prices[i])。

代码：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        // 定义下标：dp[i][0]表示第i天持有股票所能得到的最大金钱
        // dp[i][1]表示第i天不持有股票所能得到的最大金钱
        vector<vector<int>> dp(2, vector<int>(2));
        // 第0天持有股票相当于买入第0天的股票，持有金钱相当于-prices[0]
        dp[0][0] = -prices[0];
        for (int i = 1; i < prices.size(); i++)
        { 
            // 第i天持有股票有两种情况：1、第i-1天就持有股票 2、第i天买入股票
            dp[i % 2][0] = max(dp[(i - 1) % 2][0], dp[(i - 1) % 2][1]-prices[i]);
            // 第i天未持有股票有两种情况：1、第i-1天就未持有股票 2、第i天卖出股票
            dp[i % 2][1] = max(dp[(i - 1) % 2][1], dp[(i - 1) % 2][0] + prices[i]);
        }
        return dp[(prices.size() - 1) % 2][1];
    }
};