速通买卖股票的最佳时机（动态规划一网打尽）

本文为原创内容，转载请注明出处并附带原文链接。感谢您的尊重与支持！

你必须非常努力，才能看起来毫不费劲。

前言

阅读完本篇文章，你可以在力扣顺便解决以下题目：

121. 买卖股票的最佳时机(简单) 122. 买卖股票的最佳时机 II(中等)
123. 买卖股票的最佳时机 III(困难) 188. 买卖股票的最佳时机 IV(困难)
309. 买卖股票的最佳时机含冷冻期(中等) 714. 买卖股票的最佳时机含手续费(中等)

在这里插入图片描述

👊虽然在处理某些股票相关的问题时，直接使用简单的方法可能看起来更直接也更容易实现，但我希望通过采用一种更为通用的方法——比如动态规划来解决问题，即便这在开始时可能会让人觉得有些复杂或繁琐。实际上，使用如贪心算法等方法可能在解决这类问题时更加直观且效率更高。然而，我们的目标是通过动态规划这种更具普遍性的策略，帮助大家建立起解决这类问题的能力，使得在未来面对更多类似挑战时可以更加从容不迫，并且能够用最少的记忆负担应对更多的题目类型。这样做是为了长远考虑，帮助积累解决问题的通用技巧，而不是仅仅针对单一问题寻找捷径。

💪接下来，让我们探讨一下如何运用动态规划来解决这一类与股票相关的题目。一旦你掌握了通过动态规划解决一个问题的方法，之后只需要对递推公式稍作调整，并正确设置初始条件，就能够解决其他类似的问题了。这种方法的核心在于理解并应用动态规划的基本原理，从而达到举一反三的效果。

121.买卖股票的最佳时机(简单)

🐚核心思路

1）确定dp数组以及下标的含义

dp[i][0] 表示第i天持有股票所得最多现金
dp[i][1] 表示第i天不持有股票所得最多现金

注意这里说的是“持有”，“持有”不代表就是当天“买入”！也有可能是昨天就买入了，今天保持持有的状态

2）确定递推公式

如果在第 i 天持有股票 (dp[i][0])，那么有两种可能性：

  1. 我们在第 i-1 天就已经持有股票，并且在第 i 天没有进行任何操作，这意味着我们继续持有前一天的股票状态：dp[i - 1][0]。
  2. 我们在第 i 天买入股票，此时我们手中的现金减少了 prices[i]，因此现金变为 -prices[i]。

为了最大化手中的现金，我们需要在这两种情况中选择较大的值。因此，我们有：
dp[i][0] = max(dp[i - 1][0], -prices[i]);

如果在第 i 天不持有股票 (dp[i][1])，同样有两种可能性：

  1. 我们在第 i-1 天就不持有股票，并且在第 i 天没有进行任何操作，这意味着我们继续保持不持有股票的状态：dp[i - 1][1]。
  2. 我们在第 i 天卖出股票，这时我们增加的现金为股票的价格 prices[i] 加上我们在第 i-1 天持有股票时的最大现金 dp[i - 1][0]。

同样地，为了使手中的现金最大化，我们需要在这两种情况中选择较大的值。因此，我们有：
dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);

这样，我们就定义了每一天的状态转移规则，以确保在每个决策点上都能做出最佳的选择。

3）初始化

根据递推公式 dp[i][0] = max(dp[i - 1][0], -prices[i]) 和 dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0])，我们知道整个动态规划过程是从第一天的状态开始逐步推进的。

对于 dp[0][0]，它代表在第0天持有股票的情况。由于这是第一天，没有前一天的状态可以参考，所以唯一的情况就是在第0天买入股票。这意味着我们花费了 prices[0] 购买了股票，因此 dp[0][0] 的值应该是 -prices[0]（因为我们支付了这个金额来购买股票）。

而对于 dp[0][1]，它表示在第0天不持有股票的情况。在这种情况下，我们没有买入股票，所以我们的现金仍然是初始值，通常设定为 0。

因此，我们可以这样初始化：

  • dp[0][0] = -prices[0] （因为我们在第0天买入了股票）
  • dp[0][1] = 0 （因为我们没有持有股票，现金保持不变）

这样我们就明确了初始状态，可以基于此进行后续的动态规划计算，从递推公式可以看出dp[i]都是由dp[i - 1]推导出来的，所以我们从前向后遍历即可。

🌴代码实现

JAVA代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int maxProfit(int[] prices) {

        int[][] dp = new int[prices.length][2];
        // [0][0]持有   [0][1]不持有
        dp[0][0] = -prices[0];
        dp[0][1] = 0;

        for(int i=1;i<prices.length;i++){
            // 这里只能有一次买入哦！！！
            dp[i][0] = Math.max(dp[i-1][0],-prices[i]);
            dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0] + prices[i]);
        }

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

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <vector>
using namespace std;

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

        for(int i = 1; i < prices.size(); ++i){
            dp[i][0] = max(dp[i-1][0], -prices[i]);
            dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i]);
        }

        return dp[prices.size()-1][1];
    }
};

122. 买卖股票的最佳时机 II(中等)

🐚核心思路

在这道题中，股票可以买卖多次了！这也是和121. 买卖股票的最佳时机的唯一区别。重点在于递推公式的不同。

在回顾一下dp数组的含义：

dp[i][0] 表示第i天持有股票所得现金。
dp[i][1] 表示第i天不持有股票所得最多现金。

递推公式：

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

大家可以发现本题和121. 买卖股票的最佳时机 的代码几乎一样，唯一的区别在：

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

这正是因为本题的股票可以买卖多次！ 所以买入股票的时候，可能会有之前买卖的利润即：dp[i - 1][1]，所以dp[i - 1][1] - prices[i]。

🌴代码实现

JAVA代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int maxProfit(int[] prices) {
        int[][] dp = new int[prices.length][2];
        dp[0][0] = -prices[0];
        dp[0][1] = 0;

        for(int i=1;i<prices.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[prices.length-1][1];
    }

}

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int len = prices.size();
        vector<vector<int>> dp(len, vector<int>(2, 0));
        dp[0][0] -= prices[0];
        dp[0][1] = 0;
        for (int i = 1; i < len; i++) {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]); // 注意这里是和121. 买卖股票的最佳时机唯一不同的地方。
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
        }
        return dp[len - 1][1];
    }
};

123. 买卖股票的最佳时机 III(困难)

🐚核心思路

在这道题中，股票最多只能完成两笔交易。这意味着可以买卖一次，可以买卖两次，也可以不买卖。相比较于上两个题稍微复杂一点，不过就是多了几种讨论情况而已。

1）确定dp数组以及下标的含义

一天一共就有4个状态：

  • 第一次买入
  • 第一次卖出
  • 第二次买入
  • 第二次卖出

2）确定递推公式

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

3）初始化

1
2
3
4
dp[0][0] = -prices[0]; 
dp[0][1] = 0; 
dp[0][2] = -prices[0]; 
dp[0][3] = 0;

🌴代码实现

JAVA代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int maxProfit(int[] prices) {
        int[][] dp = new int[prices.length][4];
        // [0][0] 第一次买入 [0][2] 第二次买入
        dp[0][0] = -prices[0];
        dp[0][2] = -prices[0];

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

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

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.size() == 0) return 0;
        vector<vector<int>> dp(prices.size(), vector<int>(4, 0));
        dp[0][0] = -prices[0];
        dp[0][2] = -prices[0];
        for (int i = 1; i < prices.size(); i++) {
            dp[i][0] = std::max(dp[i - 1][0], -prices[i]);
            dp[i][1] = std::max(dp[i - 1][1], prices[i] + dp[i - 1][0]);
            dp[i][2] = std::max(dp[i - 1][2], dp[i - 1][1] - prices[i]);
            dp[i][3] = std::max(dp[i - 1][3], prices[i] + dp[i - 1][2]);
        }
        return dp[prices.size() - 1][3];
    }
};

188. 买卖股票的最佳时机 IV(困难)

🐚核心思路

在这道题中，股票最多可以完成 k 笔交易。相对于上一道动态规划：123.买卖股票的最佳时机III ，本题需要通过前两次的交易，来类比前k次的交易。其实也很简单，对着上一题找规律就行。但是有一点需要注意，我们要把[0][1]作为第一次买入了，为的就是处理第一次买入时的情况。
在这里插入图片描述

如果按照规律我们是不是要这样写：

1
2
3
4
5
6
for (int i = 1; i < prices.length; i++) {
    for (int j = 0; j < k*2 - 1; j += 2) {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i]);
        dp[i][j + 1] = Math.max(dp[i - 1][j + 1], dp[i - 1][j] + prices[i]);
    }
}

这肯定就矛盾了！我们最起码要从dp[0][0]开始初始化！

在这里插入图片描述

1）确定dp数组以及下标的含义

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

j的状态表示为：

0 表示不操作
1 第一次买入
2 第一次卖出
3 第二次买入
4 第二次卖出
…..
除了0以外，偶数就是卖出，奇数就是买入。

2）确定递推公式

1
2
3
4
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 为奇数是买，偶数是卖的状态。

3）初始化

dp[0][j]当j为奇数的时候都初始化为 -prices[0]

代码如下：

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

🌴代码实现

JAVA代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int maxProfit(int k, int[] prices) {
        int[][] dp = new int[prices.length][2*k+1];
        
        for (int i = 1; i < k*2; i += 2) {
            dp[0][i] = -prices[0];
        }
        // 这个地方必须要从[0][1]开始买入算起，不能从[0][0]算第一次买入
        for (int i = 1; i < prices.length; i++) {
            for (int j = 0; j < k*2 - 1; j += 2) {
                // 如果是[0][0]算第一次买入，那下面这个式子的 j 不就成负数了
                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[prices.length - 1][k*2];
    }
}

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {

        if (prices.size() == 0) return 0;
        vector<vector<int>> dp(prices.size(), vector<int>(2 * k + 1, 0));
        for (int j = 1; j < 2 * k; j += 2) {
            dp[0][j] = -prices[0];
        }
        for (int i = 1;i < prices.size(); i++) {
            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]);
            }
        }
        return dp[prices.size() - 1][2 * k];
    }
};

309. 买卖股票的最佳时机含冷冻期(中等)

在这道题中，尽可能地完成更多的交易（多次买卖一支股票），但有冷冻期，冷冻期为1天。相对于动态规划：122.买卖股票的最佳时机II ，本题加上了一个冷冻期。

🐚核心思路

1）确定dp数组以及下标的含义

本题则需要第三个状态：不持有股票（冷冻期）的最多现金。

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

j的状态为：

0：持有股票后的最多现金
1：不持有股票（能购买）的最多现金
2：不持有股票（冷冻期）的最多现金

  • dp[i][0] 表示第 i 天结束时持有股票的最大利润。
  • dp[i][1] 表示第 i 天结束时不持有股票并且不在冷冻期的最大利润。
  • dp[i][2] 表示第 i 天结束时不持有股票并且处于冷冻期的最大利润（即前一日刚卖出股票）。

2）确定递推公式

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

3）初始化

1
2
3
dp[0][0] = -prices[0];
dp[0][1] = 0;
dp[0][2] = 0;

🌴代码实现

JAVA代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int maxProfit(int[] prices) {
        int[][] dp = new int[prices.length][4];
        // [0][0]持有  [0][1]不持有  [0][2]冷冻
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        dp[0][2] = 0;

        for(int i=1;i<prices.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][2]);// 保持不持有或冷冻期结束
            dp[i][2] = dp[i-1][0] + prices[i];// 卖出后进入冷冻期
        }

        return Math.max(dp[prices.length-1][2],dp[prices.length-1][1]);
    }
}

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        vector<vector<int>> dp(prices.size(), vector<int>(3)); // [持有股票, 不持有股票, 冷冻期]

        // 初始化第一天的状态
        dp[0][0] = -prices[0]; // 持有股票的最大利润
        dp[0][1] = 0; // 不持有股票的最大利润
        dp[0][2] = 0; // 第一天不可能处于冷冻期

        for (size_t i = 1; i < prices.size(); ++i) {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]); // 保持持有或买入
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][2]); // 保持不持有或冷冻期结束
            dp[i][2] = dp[i - 1][0] + prices[i]; // 卖出后进入冷冻期
        }

        // 最终结果是不持有股票并且不在冷冻期的最大利润
        return max(dp[prices.size() - 1][2], dp[prices.size() - 1][1]);
    }
};

714. 买卖股票的最佳时机含手续费(中等)

🐚核心思路

这个题没什么难的，相比于122. 买卖股票的最佳时机II 无非就是多了一步最后计算手续费的步骤而已。

递推公式这里：

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

🌴代码实现

JAVA代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int maxProfit(int[] prices, int fee) {
        int[][] dp = new int[prices.length][2];
        dp[0][0] = -prices[0];
        dp[0][1] = 0;

        for(int i=1;i<prices.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] - fee);
        }

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

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int n = prices.size();
        vector<vector<int>> dp(n, vector<int>(2, 0));
        dp[0][0] -= prices[0]; // 持股票
        for (int i = 1; i < n; i++) {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee);
        }
        return max(dp[n - 1][0], dp[n - 1][1]);
    }
};