买卖股票类型算法总结

最近做动态规划的题目，发现了一类题叫买卖股票，今天准备来总结一下这类题型，一共有6道题，链接如下：

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

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

• 123. 买卖股票的最佳时机 III

• 188. 买卖股票的最佳时机 IV

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

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

理论阐述

首先介绍一些符号：

用 n 表示股票价格数组的长度；
用 i 表示第 i 天（i 的取值范围是 0 到 n - 1）；
用 k 表示允许的最大交易次数；
用 T[i][k]表示在第 i 天结束时，最多进行 k 次交易的情况下可以获得的最大收益。

基准情况是显而易见的：T[-1][k] = T[i][0] = 0，表示没有进行股票交易时没有收益（注意第一天对应 i = 0，因此 i = -1 表示没有股票交易）。现在如果可以将 T[i][k] 关联到子问题，例如 T[i - 1][k]、T[i][k - 1]、T[i - 1][k - 1] 等子问题，就能得到状态转移方程，并对这个问题求解。如何得到状态转移方程呢？

最直接的办法是看第 i 天可能的操作。有多少个选项？答案是三个：买入、卖出、休息。应该选择哪个操作？答案是：并不知道哪个操作是最好的，但是可以通过计算得到选择每个操作可以得到的最大收益。假设没有别的限制条件，则可以尝试每一种操作，并选择可以最大化收益的一种操作。但是，题目中确实有限制条件，规定不能同时进行多次交易，因此如果决定在第 i 天买入，在买入之前必须持有 0 份股票，如果决定在第 i 天卖出，在卖出之前必须恰好持有 1 份股票。持有股票的数量是上文提及到的隐藏因素，该因素影响第 i 天可以进行的操作，进而影响最大收益。

因此对 T[i][k] 的定义需要分成两项：

T[i][k][0] 表示在第 i 天结束时，最多进行 k 次交易且在进行操作后持有 0 份股票的情况下可以获得的最大收益；
T[i][k][1] 表示在第 i 天结束时，最多进行 k 次交易且在进行操作后持有 1 份股票的情况下可以获得的最大收益。

基准情况：

T[-1][k][0] = 0, T[-1][k][1] = -Infinity
T[i][0][0] = 0, T[i][0][1] = -Infinity

状态转移方程：

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

基准情况中，T[-1][k][0] = T[i][0][0] = 0 的含义和上文相同，T[-1][k][1] = T[i][0][1] = -Infinity 的含义是在没有进行股票交易时不允许持有股票。

对于状态转移方程中的 T[i][k][0]，第 i 天进行的操作只能是休息或卖出，因为在第 i 天结束时持有的股票数量是 0。T[i - 1][k][0] 是休息操作可以得到的最大收益，T[i - 1][k][1] + prices[i] 是卖出操作可以得到的最大收益。注意到允许的最大交易次数是不变的，因为每次交易包含两次成对的操作，买入和卖出。只有买入操作会改变允许的最大交易次数。

对于状态转移方程中的 T[i][k][1]，第 i 天进行的操作只能是休息或买入，因为在第 i 天结束时持有的股票数量是 1。T[i - 1][k][1] 是休息操作可以得到的最大收益，T[i - 1][k - 1][0] - prices[i] 是买入操作可以得到的最大收益。注意到允许的最大交易次数减少了一次，因为每次买入操作会使用一次交易。

为了得到最后一天结束时的最大收益，可以遍历股票价格数组，根据状态转移方程计算 T[i][k][0] 和 T[i][k][1] 的值。最终答案是 T[n - 1][k][0]，因为结束时持有 0 份股票的收益一定大于持有 1 份股票的收益。

实际应用

下面结合具体题目进行阐述

上述六个股票问题是根据 k 的值进行分类的，其中 k 是允许的最大交易次数。最后两个问题有附加限制，包括「冷冻期」和「手续费」。通解可以应用于每个股票问题。

情况一：k = 1

情况一对应的题目是121. 买卖股票的最佳时机。

对于情况一，每天有两个未知变量：T[i][1][0] 和 T[i][1][1]，状态转移方程如下：

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

第二个状态转移方程利用了 T[i][0][0] = 0。

根据上述状态转移方程，可以写出时间复杂度为 O(n)和空间复杂度为 O(n)的解法。

class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        int length = prices.length;
        int[][] dp = new int[length][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (int i = 1; i < length; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
        }
        return dp[length - 1][0];
    }
}

这题其实还可以使用贪心的解法，只在最低的价格买入，然后计算卖出的最高价格

class Solution {
    public int maxProfit(int[] prices) {
        int max = 0;
        int minPrice = Integer.MAX_VALUE;
        for(int i = 0; i < prices.length; i++) {
            minPrice = Math.min(prices[i], minPrice);
            max = Math.max(prices[i]- minPrice, max);
        }
        return max;
    }
}

情况二：k 为正无穷

情况二对应的题目是122. 买卖股票的最佳时机 II。

如果 k 为正无穷，则 k 和 k - 1 可以看成是相同的，因此有 T[i - 1][k - 1][0] = T[i - 1][k][0] 和 T[i - 1][k - 1][1] = T[i - 1][k][1]。每天仍有两个未知变量：T[i][k][0] 和 T[i][k][1]，其中 k 为正无穷，状态转移方程如下：

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

第二个状态转移方程利用了 T[i - 1][k - 1][0] = T[i - 1][k][0]

根据上述状态转移方程，可以写出时间复杂度为 O(n)和空间复杂度为 O(n) 的解法。

class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        int length = prices.length;
        int[][] dp = new int[length][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (int i = 1; i < length; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }
        return dp[length - 1][0];
    }
}

可以看出和第一种情况的区别仅仅是在 dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i])这里dp[i - 1][0]不一定等于0了。

情况三：k = 2

情况三对应的题目是123. 买卖股票的最佳时机 III。

情况三和情况一相似，区别之处是，对于情况三，每天有四个未知变量：T[i][1][0]、T[i][1][1]、T[i][2][0]、T[i][2][1]，状态转移方程如下：

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

第四个状态转移方程利用了 T[i][0][0] = 0。

根据上述状态转移方程，可以写出时间复杂度为 O(n)和空间复杂度为 O(n)的解法。

class Solution {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        // 边界判断, 题目中 length >= 1, 所以可省去
        if (prices.length == 0) return 0;

        /*
         * 定义 5 种状态:
         * 0: 没有操作, 1: 第一次买入, 2: 第一次卖出, 3: 第二次买入, 4: 第二次卖出
         */
        int[][] dp = new int[len][5];
        dp[0][1] = -prices[0];
        // 初始化第二次买入的状态是确保 最后结果是最多两次买卖的最大利润
        dp[0][3] = -prices[0];

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

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

情况四：k 为任意值

情况四对应的题目是188. 买卖股票的最佳时机 IV。

使用二维数组 dp[i][j] ：第i天的状态为j，所剩下的最大现金是dp[i][j]

j的状态表示为：

• 0 表示不操作
• 1 第一次买入
• 2 第一次卖出
• 3 第二次买入
• 4 第二次卖出
• …..

大家应该发现规律了吧 ，除了0以外，偶数就是卖出，奇数就是买入。题目要求是至多有K笔交易，那么j的范围就定义为 2 * k + 1 就可以了。

还要强调一下：dp[i][1]，表示的是第i天，买入股票的状态，并不是说一定要第i天买入股票

达到dp[i][1]状态，有两个具体操作：

• 操作一：第i天买入股票了，那么dp[i][1] = dp[i - 1][0] - prices[i]
• 操作二：第i天没有操作，而是沿用前一天买入的状态，即：dp[i][1] = dp[i - 1][1]

选最大的，所以 dp[i][1] = max(dp[i - 1][0] - prices[i], dp[i - 1][1]);

同理dp[i][2]也有两个操作：

• 操作一：第i天卖出股票了，那么dp[i][2] = dp[i - 1][1] + prices[i]
• 操作二：第i天没有操作，沿用前一天卖出股票的状态，即：dp[i][2] = dp[i - 1][2]

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

同理可以类比剩下的状态，代码如下：

for (int j = 0; j < 2 * k - 1; j += 2) {
    dp[i][j + 1] = max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]);
    dp[i][j + 2] = max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]);
}

本题和123.买卖股票的最佳时机III最大的区别就是这里要类比j为奇数是买，偶数是卖的状态

dp数组如何初始化

第0天没有操作，这个最容易想到，就是0，即：dp[0][0] = 0;

第0天做第一次买入的操作，dp[0][1] = -prices[0];

第0天做第一次卖出的操作，这个初始值应该是多少呢？

首先卖出的操作一定是收获利润，整个股票买卖最差情况也就是没有盈利即全程无操作现金为0，

从递推公式中可以看出每次是取最大值，那么既然是收获利润如果比0还小了就没有必要收获这个利润了。

所以dp[0][2] = 0;

第0天第二次买入操作，初始值应该是多少呢？

不用管第几次，现在手头上没有现金，只要买入，现金就做相应的减少。

第二次买入操作，初始化为：dp[0][3] = -prices[0];

所以同理可以推出dp[0][j]当j为奇数的时候都初始化为 -prices[0]

综上所述，代码如下：

class Solution {
    public int maxProfit(int k, int[] prices) {
        if (prices.length == 0) return 0;

        // [天数][股票状态]
        // 股票状态: 奇数表示第 k 次交易持有/买入, 偶数表示第 k 次交易不持有/卖出, 0 表示没有操作
        int len = prices.length;
        int[][] dp = new int[len][k*2 + 1];
        
        // dp数组的初始化
        for (int i = 1; i < k*2; i += 2) {
            dp[0][i] = -prices[0];
        }
        for (int i = 1; i < len; i++) {
            for (int j = 0; j < k*2 - 1; j += 2) {
                dp[i][j + 1] = Math.max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]);
                dp[i][j + 2] = Math.max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]);
            }
        }
        return dp[len - 1][k*2];
    }
}

情况五：k 为正无穷但有冷却时间

情况五对应的题目是「309. 最佳买卖股票时机含冷冻期」。

相对于122. 买卖股票的最佳时机 II，本题加上了一个冷冻期

定义状态数组dp[i][j]，第i天状态为j，所剩的最多现金为dp[i][j]。

具体可以区分出如下四个状态：

• 状态一：买入股票状态（今天买入股票，或者是之前就买入了股票然后没有操作）
• 卖出股票状态，这里就有两种卖出股票状态
  • 状态二：两天前就卖出了股票，度过了冷冻期，一直没操作，今天保持卖出股票状态
  • 状态三：今天卖出了股票
• 状态四：今天为冷冻期状态，但冷冻期状态不可持续，只有一天

达到买入股票状态（状态一）即：dp[i][0]，有两个具体操作：

• 操作一：前一天就是持有股票状态（状态一），dp[i][0] = dp[i - 1][0]
• 操作二：今天买入了，有两种情况
  • 前一天是冷冻期（状态四），dp[i - 1][3] - prices[i]
  • 前一天是保持卖出股票状态（状态二），dp[i - 1][1] - prices[i]

所以操作二取最大值，即：max(dp[i - 1][3], dp[i - 1][1]) - prices[i]

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

达到保持卖出股票状态（状态二）即：dp[i][1]，有两个具体操作：

• 操作一：前一天就是状态二
• 操作二：前一天是冷冻期（状态四）

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

达到今天就卖出股票状态（状态三），即：dp[i][2] ，只有一个操作：

• 操作一：昨天一定是买入股票状态（状态一），今天卖出

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

达到冷冻期状态（状态四），即：dp[i][3]，只有一个操作：

• 操作一：昨天卖出了股票（状态三）

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

综合递推代码如下：

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

代码如下

class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length < 2) {
            return 0;
        }
        int[][] dp = new int[prices.length][2];

        // bad case
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        dp[1][0] = Math.max(dp[0][0], dp[0][1] + prices[1]);
        dp[1][1] = Math.max(dp[0][1], -prices[1]);

        for (int i = 2; i < prices.length; i++) {
            // dp公式
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 2][0] - prices[i]);
        }

        return dp[prices.length - 1][0];
    }
}

情况六：k 为正无穷但有手续费

情况六对应的题目是714. 买卖股票的最佳时机含手续费。

相对于122. 买卖股票的最佳时机II，本题只需要在计算卖出操作的时候减去手续费就可以了，代码几乎是一样的。

如果第i天持有股票即dp[i][0]， 那么可以由两个状态推出来

• 第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即：dp[i - 1][0]
• 第i天买入股票，所得现金就是昨天不持有股票的所得现金减去 今天的股票价格 即：dp[i - 1][1] - prices[i]

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

在来看看如果第i天不持有股票即dp[i][1]的情况， 依然可以由两个状态推出来

• 第i-1天就不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金 即：dp[i - 1][1]
• 第i天卖出股票，所得现金就是按照今天股票价格卖出后所得现金，注意这里需要有手续费了即：dp[i - 1][0] + prices[i] - fee

所以：dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee);

代码如下：

class Solution {
 public int maxProfit(int[] prices, int fee) {
    int len = prices.length;
    // 0 : 持股（买入）
    // 1 : 不持股（售出）
    // dp 定义第i天持股/不持股 所得最多现金
    int[][] dp = new int[len][2];
    dp[0][0] = -prices[0];
    for (int i = 1; i < len; i++) {
        dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
        dp[i][1] = Math.max(dp[i - 1][0] + prices[i] - fee, dp[i - 1][1]);
    }
    return Math.max(dp[len - 1][0], dp[len - 1][1]);
}
}

// 一维数组优化
class Solution {
    public int maxProfit(int[] prices, int fee) {
    int[] dp = new int[2];
    dp[0] = -prices[0];
    dp[1] = 0;
    for (int i = 1; i <= prices.length; i++) {
      dp[0] = Math.max(dp[0], dp[1] - prices[i - 1]);
      dp[1] = Math.max(dp[1], dp[0] + prices[i - 1] - fee);
    }
    return dp[1];
    }
}

此题还可以使用贪心算法

如果使用贪心策略，就是最低值买，最高值（如果算上手续费还盈利）就卖。

此时无非就是要找到两个点，买入日期，和卖出日期。

• 买入日期：其实很好想，遇到更低点就记录一下。
• 卖出日期：这个就不好算了，但也没有必要算出准确的卖出日期，只要当前价格大于（最低价格+手续费），就可以收获利润，至于准确的卖出日期，就是连续收获利润区间里的最后一天（并不需要计算是具体哪一天）。

所以我们在做收获利润操作的时候其实有三种情况：

• 情况一：收获利润的这一天并不是收获利润区间里的最后一天（不是真正的卖出，相当于持有股票），所以后面要继续收获利润。
• 情况二：前一天是收获利润区间里的最后一天（相当于真正的卖出了），今天要重新记录最小价格了。
• 情况三：不作操作，保持原有状态（买入，卖出，不买不卖）

代码如下：

// 贪心思路
class Solution {
    public int maxProfit(int[] prices, int fee) {
        int buy = prices[0] + fee;
        int sum = 0;
        for (int p : prices) {
            if (p + fee < buy) {
                buy = p + fee;
            } else if (p > buy){
                sum += p - buy;
                buy = p;
            }
        }
        return sum;
    }
}