LeetCode 买卖股票系列问题总结

LeetCode 上共有 6 道有关买卖股票的系列问题：

#121 买卖股票的最佳时机
#122 买卖股票的最佳时机 II
#123 买卖股票的最佳时机 III
#188 买卖股票的最佳时机 IV
#309 最佳买卖股票时机含冷冻期
#714 买卖股票的最佳时机含手续费

本文就对这类问题的动态规划解法做一个总结。

#121 买卖股票的最佳时机

设 dp[0][i] 为第 i 天持有股票时拥有的最大现金（不一定是第 i 天刚购入，也可能是第 i 天就购入股票并持有至第 i 天），设 dp[1][i] 为第 i 天未持有股票时拥有的最大现金，所得状态转移方程为：

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

由于只能买卖一次股票，所以 dp[0][i] 的状态只能由 dp[0][i-1]（第 i 天前已经持有）和 -prices[i]（第 i 天刚好买入）转移而来。

dp 数组初始化方面， dp[0][0] 代表第 0 天已经购买股票，那么 dp[0][0] 就应该被初始化为 -prices[i]；dp[1][0] 显然应初始化为 0。最终实现的循环应从下标 1 开始递推。

代码实现如下：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<vector<int>> dp(2, vector<int>(n, 0));
        dp[0][0] = -prices[0];
        dp[1][0] = 0;

        for (int i = 1; i < n; i++) {
            dp[0][i] = max(dp[0][i - 1], -prices[i]);
            dp[1][i] = max(dp[1][i - 1], dp[0][i - 1] + prices[i]);
        }
        return dp[1][n - 1]; // 最终股票肯定是要卖出的，所以返回的是dp[1][n - 1]
    }
};

#122 买卖股票的最佳时机 II

状态定义与 I 完全相同，只是状态转移方程有所不同，准确说是 dp[0][i] 的状态可以由 dp[0][i-1]（第 i 天前已经持有）和 dp[1][i-1] – prices[i] 转移而来，即：

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

不难写出如下代码。

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

#123 买卖股票的最佳时机 III

由于最多完成 2 笔交易，我们可以把交易的过程划分为 5 种状态：

dp[0][i]：第 i 天不进行任何操作（可理解为从未购入股票的状态）时拥有的最大现金。
dp[1][i]：第 i 天恰好第一次买入股票，或第一次买入后一直持有股票时拥有的最大现金。
dp[2][i]：第 i 天处于第一次卖出股票，或第一次卖出股票后不持有股票时拥有的最大现金。
dp[3][i]：第 i 天恰好第二次买入股票，或第二次买入后一直持有股票时拥有的最大现金。
dp[4][i]：第 i 天处于第二次卖出股票，或第二次卖出股票后不持有股票时拥有的最大现金。

dp[1][i] 可以由 dp[1][i-1]（第 i 天前第一次买入股票后一直持有的状态） 和 dp[0][i-1]（从未购入过股票的状态）转移而来，状态转移方程为：

dp[1][i] = max(dp[1][i - 1], dp[0][i - 1] - prices[i]);

dp[2][i] 可以由 dp[2][i-1]（第 i 天前第一次卖出股票后不持有股票的状态） 和 dp[1][i-1] 转移而来，状态转移方程为：

dp[2][i] = max(dp[2][i - 1], dp[1][i - 1] + prices[i]);

同理，dp[3][i] 和 dp[4][i] 的状态转移方程为：

dp[3][i] = max(dp[3][i - 1], dp[2][i - 1] - prices[i]);
dp[4][i] = max(dp[4][i - 1], dp[3][i - 1] + prices[i]);

dp 数组初始化方面，dp[0][i] 的值显然都为 0，不进行任何操作肯定是没有现金的；dp[2][0] 与 dp[4][0] 应为 0，因为第 0 天什么都不做肯定持有最大的现金 0，若第 0 天买入则持有的现金肯定变成了负数；dp[1][0] 根据前面 I 和 II 的讨论也应初始化为 -prices[i]；dp[3][0]，笔者一开始也初始化为 0，想着第一次还没有交易怎么能谈第二次买入呢？实际上是不对的，可以看作第 0 天第一次买入并卖出，然后再买入一次（第二次买入），故初始化为 -prices[i]。

实现代码如下：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<vector<int>> dp(5, vector<int>(n, 0));
        // dp的第0行已经在上面初始化全0
        dp[1][0] = -prices[0];
        dp[2][0] = 0;
        dp[3][0] = -prices[0];
        dp[4][0] = 0;

        for(int i = 1; i < n; i ++) {
            dp[0][i] = dp[0][i - 1];
            dp[1][i] = max(dp[1][i - 1], dp[0][i - 1] - prices[i]);
            dp[2][i] = max(dp[2][i - 1], dp[1][i - 1] + prices[i]);
            dp[3][i] = max(dp[3][i - 1], dp[2][i - 1] - prices[i]);
            dp[4][i] = max(dp[4][i - 1], dp[3][i - 1] + prices[i]);
        }

        return dp[4][n - 1];
    }
};

#188 买卖股票的最佳时机 IV

和 III 类似，只不过变成了最多交易 k 次。从 III 的递推公式我们可知，奇数行和偶数行的状态转移方程是有规律的，即：

dp[i][j] = max(dp[i][j - 1], dp[i - 1][j - 1] - prices[j]); // i为奇数
dp[i][j] = max(dp[i][j - 1], dp[i - 1][j - 1] + prices[j]); // i为偶数

dp 数组初始化方面，除了第 0 行还是全 0 外，dp[i][0] 也有奇偶的规律，即当 i 为奇数时初始化为 -prices[0]，i 为偶数时初始化为 0。

代码实现如下：

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        vector<vector<int>> dp(2 * k + 1, vector<int>(n, 0)); // 最多买卖k次，那么开2*k+1行数组
        for(int i = 1; i < 2 * k + 1; i += 2) { // 对奇数行进行初始化，偶数行默认已经为0
            dp[i][0] = -prices[0];
        }

        for(int i = 1; i < 2 * k + 1; i += 2) {
            for(int j = 1; j < n; j ++) { // 分奇偶进行递推
                dp[i][j] = max(dp[i][j - 1], dp[i - 1][j - 1] - prices[j]);
                dp[i + 1][j] = max(dp[i + 1][j - 1], dp[i][j - 1] + prices[j]);
            }
        }

        return dp[2 * k][n - 1];
    }
};

#309 最佳买卖股票时机含冷冻期

加入了冷冻期后，买卖股票的状态就能划分为如下四种：

dp[0][i]：第 i 天持有股票时拥有的最大现金。
dp[1][i]：第 i 天未持有股票、且当天已经度过冷冻期时拥有的最大现金。
dp[2][i]：第 i 天刚好卖出股票时拥有的最大现金。
dp[3][i]：第 i 天未持有股票、且当天恰好为冷冻期时拥有的最大现金。

dp[0][i] 可由 dp[0][i-1]、dp[1][i-1]、dp[3][i-1] 三种状态转移而来，状态转移方程为：

dp[0][i] = max(dp[0][i - 1], dp[1][i - 1] - prices[i], dp[3][i - 1] - prices[i]);

dp[1][i] 可由 dp[1][i-1] 与 dp[3][i-1] 转移而来，状态转移方程为：

dp[1][i] = max(dp[1][i - 1], dp[3][i - 1]);

dp[2][i] 只能由 dp[0][i-1] 转移而来，状态转移方程为：

dp[2][i] = dp[0][i - 1] + prices[i];

dp[3][i] 只能由 dp[2][i-1] 转移而来，状态转移方程为：

dp[3][i] = dp[2][i - 1];

dp 数组初始化方面，dp[0][0] 应为 -prices[0]，dp[1][0]、dp[2][0]、dp[3][0] 均初始化为 0。

代码实现如下：

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

        return max(dp[1][n - 1], max(dp[2][n - 1], dp[3][n - 1])); // 注意最后的结果应该是三个结果取最大
    }
};

#714 买卖股票的最佳时机含手续费

这个就比较简单了，在 #122 买卖股票的最佳时机 II 的基础上，卖股票的时候多减手续费就行。

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int n = prices.size();
        vector<vector<int>> dp(2, vector<int>(n, 0));
        dp[0][0] = -prices[0];
        dp[1][0] = 0;
        for (int i = 1; i < n; i++) {
            dp[0][i] = max(dp[0][i - 1], dp[1][i - 1] - prices[i]);
            dp[1][i] = max(dp[1][i - 1], dp[0][i - 1] + prices[i] - fee); // 卖出时减去手续费
        }
        return dp[1][n - 1];
    }
};