多状态动态规划：买卖股票最佳时机系列问题解析

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

分析

使用动态规划解决。

状态表示

由于有「买入」「可交易」「冷冻期」三个状态，因此我们可以选择用三个数组，其中：

• dp[i][0] 表示：第 i 天结束后，处于「买入」状态，此时的最大利润。
• dp[i][1] 表示：第 i 天结束后，处于「可交易」状态，此时的最大利润。
• dp[i][2] 表示：第 i 天结束后，处于「冷冻期」状态，此时的最大利润。

状态转移方程

1. 处于买入状态的时候，我们现在有股票，此时不能买股票，只能继续持有股票，或者卖出股票；
2. 处于卖出状态的时候：
   • 如果在冷冻期，不能买入。
   • 如果不在冷冻期，才能买入。

画出状态图

根据状态图可以得出：

买入->买入：什么都不干 买入->卖出：买入股票 对应代码：a[i]=max(a[i-1],c[i-1]-prices[i-1]);

卖出->卖出：什么都不干 卖出->冷冻期：卖出股票 对应代码：b[i]=max(b[i-1],a[i-1]+prices[i-1]);

冷冻期->冷冻期：什么都不干 冷冻期->买入：冷冻期结束 对应代码：c[i]=max(c[i-1],b[i-1]);

代码

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<int> a(n + 1); // 买入
        vector<int> b(n + 1); // 卖出
        vector<int> c(n + 1); // 冷冻
        
        a[0] = -prices[0];
        for (int i = 1; i <= n; i++) {
            a[i] = max(a[i - 1], c[i - 1] - prices[i - 1]);
            b[i] = max(b[i - 1], a[i - 1] + prices[i - 1]);
            c[i] = max(c[i - 1], b[i - 1]);
        }
        return max(b[n], c[n]); // 从卖出和冷冻期中选出最大值，因为买入状态肯定不是最大值，因为还有股票没有卖出。
    }
};

---

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

分析

使用动态规划解决。与买卖股票的最佳时机含冷冻期问题相似，我们直接画出状态图写状态方程。

状态图

买入->买入：什么都不干 买入->卖出：买入股票 对应代码：a[i]=max(a[i-1],c[i-1]-prices[i-1]);

卖出->卖出：什么都不干 卖出->买入：卖出股票并支付手续费 对应代码：b[i]=max(b[i-1],a[i-1]+prices[i-1]-fee);

代码

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int n = prices.size();
        vector<int> a(n + 1); // 买入
        vector<int> b(n + 1); // 卖出
        a[0] = -prices[0];
        for (int i = 1; i <= n; i++) {
            a[i] = max(a[i - 1], b[i - 1] - prices[i - 1]);
            b[i] = max(b[i - 1], a[i - 1] + prices[i - 1] - fee);
        }
        return b[n];
    }
};

---

买卖股票的最佳时机 III

状态表示

这里我们选择比较常用的方式，以某个位置为结尾，结合题目要求，定义一个状态表示：由于有「买入」「可交易」两个状态，因此我们可以选择用两个数组。但是这道题里面还有交易次数的限制，因此我们还需要再加上一维，用来表示交易次数。其中：

• f[i][j] 表示：第 i 天结束后，完成了 j 次交易，处于「买入」状态，此时的最大利润；
• g[i][j] 表示：第 i 天结束后，完成了 j 次交易，处于「卖出」状态，此时的最大利润。

状态转移方程

A. 对于 f[i][j]，我们有两种情况到这个状态：

1. 在 i - 1 天的时候，交易了 j 次，处于「买入」状态，第 i 天啥也不干即可。此时最大利润为：f[i - 1][j]；
2. 在 i - 1 天的时候，交易了 j 次，处于「卖出」状态，第 i 天的时候把股票买了。此时的最大利润为：g[i - 1][j] - prices[i]。 综上，我们要的是「最大利润」，因此是两者的最大值：f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i])。

B. 对于 g[i][j]，我们也有两种情况可以到达这个状态：

1. 在 i - 1 天的时候，交易了 j 次，处于「卖出」状态，第 i 天啥也不干即可。此时的最大利润为：g[i - 1][j]；
2. 在 i - 1 天的时候，交易了 j - 1 次，处于「买入」状态，第 i 天把股票卖了，然后就完成了 j 比交易。此时的最大利润为：f[i - 1][j - 1] + prices[i]。但是这个状态不一定存在，要先判断一下。 综上，我们要的是最大利润，因此状态转移方程为： g[i][j] = g[i - 1][j]; if(j >= 1) g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);

代码

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        const int INF = 0x3f3f3f3f;
        int n = prices.size();
        vector<vector<int>> f(n + 1, vector<int>(3, -INF)); // 买
        vector<vector<int>> g(n + 1, vector<int>(3, -INF)); // 卖
        f[0][0] = -prices[0];
        g[0][0] = 0;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < 3; j++) {
                f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);
                g[i][j] = g[i - 1][j];
                if (j - 1 >= 0) {
                    g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < 3; i++) {
            ans = max(ans, g[n - 1][i]);
        }
        return ans;
    }
};