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];
    }
};

发表回复

您的电子邮箱地址不会被公开。