“买卖股票的最佳时机” 系列——我来教你稳赚不亏~

╰+哭是因爲堅強的太久メ 2023-09-23 22:46 40阅读 0赞

**目录**

前言

一、买卖股票的最佳时机 ——>指定次数交易（1次）

1.1、dp定义

1.2、递推公式

1.3、遍历顺序

1.4、初始化

1.5、解题代码

二、买卖股票的最佳时机II ——>交易到结束

2.1、分析

2.2、解题代码

三、买股票的最佳时机III ——>指定次数交易（2次）

3.1、dp定义

3.2、递推公式

3.3、遍历顺序

3.4、初始化

3.5、解题代码

四、买股票的最佳时机IV ——>指定次数交易（k次）

4.1、分析

4.2、解题代码

五、最佳买卖股票时机含冷冻期 ——>交易到结束（含冷冻期）

5.1、dp定义

5.2、递推公式

5.3、遍历顺序

5.4、初始化

5.5、解题代码

六、买卖股票的最佳时机含手续费 ——>交易到结束（含手续费）

6.1、分析

6.2、解题代码

小结

--------------------

# 前言 #

本篇题目虽然可以使用其他方法，如暴力枚举、贪心来解，但是只是针对特定场景的问题才可以，所以这里我将用动态规划的方法来教你，如何买股票，才能稳赚不亏！

--------------------

# 一、买卖股票的最佳时机 ——>指定次数交易（1次） #

> 题目描述：

![f6344cc181c2453f9002e2e69cd6ed0d.png][]

题目来源：[121. 买卖股票的最佳时机][121.]

> 解题方法：

## 1.1、dp定义 ##

> 分析：

第 i 天的股票无非就是两种状态，**一种是这天持有股票dp\[i\]\[0\]，另一种是这天不持有股票dp\[i\]\[1\]，那么因该用一个二维数组表示第 i 天的状态（一维很难表示一天存在的两种状态）。**

这里可能有人要问了：为什么不是定义为第i天买入股票，或是第i天卖出股票？

若是这样定义，就少了一些状态（保持卖出和买入状态），例如你定义第 i 天卖出股票，那么你第 i + 1 天的状态就是一个未知的状态（因为这一天还没有来临），当这i + 1天真的来临的时候你还要去定义它是卖出还是持有吗？一定要注意本题买卖股票只交易一次；

那么如果你是定义为**“持有或不持有”**，那么他状态就能延续下去，进行推导。**（这是这类题解题的关键）**

> 状态定义：

dp\[i\]\[0\]表示第 i 天持有股票的最大利润，dp\[i\]\[1\]表示第 i 天不持有股票的最大利润，那么最终问题的解就是max(dp\[len - 1\]\[0\], dp\[len - 1\]\[1\])；（实际上这里的解因该是dp\[len - 1\]\[1\]，因为你最后一天一定是一个股票不持有的状态，才是利润最大的！）

## 1.2、递推公式 ##

> 分析：

**dp\[i\]\[0\]表示第 i 天持有股票**，有两种情况：

1. 第 i 天才买的股票，所以第 i 天持有股票 --> -prices\[i\]。（这里直接是-prices\[i\]，是因为本题中买卖股票的交易只有一次，**不存在i - 1天前交易获利了今天继续买股票的情况，也就是dp\[i - 1\]\[1\] -prices\[i\]）**

2. 前 i - 1 天中的某一天买的股票，所以第 i 天持有 --> dp\[i - 1\]\[0\]。

**dp\[i\]\[1\]表示第i天不持有股票**，有两种情况：

1. 之前一直持有股票，第 i 天才卖出股票，所以第 i 天不持有股票 --> dp\[i - 1\]\[0\] + prices\[i\]。（前i - 1天持有股票的最大利润 + 第 i 天卖出所赚的利润）；

2. 前 i - 1天中的某一天卖出了，所以第 i 天不持有股票 --> dp\[i - 1\]\[1\]。

> 状态转移方程：

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\]);

## 1.3、遍历顺序 ##

由上面的递推公式可以知道，第 i 天的状态是由前i - 1天的状态推导而来，所以是顺序遍历；

## 1.4、初始化 ##

> 分析：

由递推公式中可以看出，每一个状态都需要依赖于前面的一个状态推导而来，那么一直往回推，推导根源就是dp\[0\]\[0\]和dp\[0\]\[1\]；

dp\[0\]\[0\]表示第0天持有股票，那么就是第一个股票的价钱；

dp\[0\]\[1\]表示都0天不持有股票，那么就是0；

> 初始化：

dp\[0\]\[0\] = prices\[0\];

dp\[0\]\[1\] = 0;

## 1.5、解题代码 ##

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], -prices[i]);
                dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
            }
            return dp[prices.length - 1][1];
        }
    }

--------------------

# 二、买卖股票的最佳时机II ——>交易到结束 #

> 题目描述：

![d843c33ade36452bb0d7bc15f6b26b3a.png][]

题目来源：[122. 买卖股票的最佳时机 II][122. _ II]

## 2.1、分析 ##

与买股票的最佳时机I，唯一的差别就是本题买卖股票的次数可以是多次，那么不同点就是在状态转移方程上。

实际上在那道题中，我就已经说明了，状态转移方程的区别，如果不太理解可以翻回去看看；

> 递推公式如下：

第i天持有股票：

dp\[i\]\[0\] = Math.max(dp\[i - 1\]\[0\], **dp\[i - 1\]\[1\] - prices\[i\]**);

第i天不持有股票：

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

## 2.2、解题代码 ##

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++) {
                //第i天持有股票
                dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
                //第i天不持有股票
                dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
            }
            return dp[prices.length - 1][1];
        }
    }

--------------------

# 三、买股票的最佳时机III ——>指定次数交易（2次） #

> 题目描述：

![8d1f598cdbae44e6a2aa789d1e13f3aa.png][]

题目来源：[123. 买卖股票的最佳时机 III][123. _ III]

## 3.1、dp定义 ##

与前两道题唯一的区别是，本题买卖股票的交易只能进行两次，那么这里要定义的状态就需要多一些了；（为什么会像下方这样定义，在第一题中有详细分析）

dp\[0\]\[0\]：什么都不操作。（这个状态可有可无，只是为了后面递推公式更加完整）；

dp\[0\]\[1\]：第一次持有股票。

dp\[0\]\[2\]：第一次不持有股票。

dp\[0\]\[3\]：第二次持有股票。

dp\[0\]\[4\]：第二次不持有股票。

## 3.2、递推公式 ##

> 分析：

dp\[i\]\[0\]：什么都不操作，那就可以表示为前一天的状态 --> dp\[i - 1\]\[0\]。

dp\[i\]\[1\]：可以是前i - 1就已经持有了第一次的股票 --> dp\[i - 1\]\[1\]；也可以是今天才第一次买股票（那么前i - 1天一定是什么都没有做） --> dp\[i - 1\]\[0\] - prices\[i\]。

dp\[i\]\[2\]：可以是前i - 1天不持有第一次的股票 --> dp\[i - 1\]\[2\]；也可以是前i - 1天持有第一次的股票，在第i天的时候才卖出 --> dp\[i - 1\]\[1\] + prices\[i\]；

dp\[i\]\[3\]：可以是前i - 1天就持有了第二次的股票 --> dp\[i - 1\]\[3\]；也可以是前i - 1天不持有第二的股票，第i天才持有（那么一定是前i - 1天中的某一天已经不持有第一次的股票了） --> dp\[i - 1\]\[2\] - prices\[i\]；

dp\[i\]\[4\]：可以是前i - 1天不持有第二次的股票 --> dp\[i - 1\]\[4\]；也可以是前i - 1天持有第二次的股票，接着第i天卖出第二次的股票 --> dp\[i - 1\]\[3\] + prices\[i\]；

> 状态转移方程：

dp\[i\]\[0\] = dp\[i - 1\]\[0\];

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

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

dp\[i\]\[3\] = Math.max(dp\[i - 1\]\[3\], dp\[i - 1\]\[2\] - prices\[i\]);

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

## 3.3、遍历顺序 ##

由上面的递推公式可以知道，第 i 天的状态是由前i - 1天的状态推导而来，所以是顺序遍历；

## 3.4、初始化 ##

> 分析：

根据状态转移方程可以看出，每一个状态都是由前一个状态推出来的，一直往前推，也就是说，我们应该要初始化dp\[0\]\[0~4\]；

**注意：这里需要提前知道的一点是，题目中没有明确规定，“股票不能当天买入天卖出”，实际上，“这天什么都不干” 就等同于 “股票当天买入当天卖出”，她两的利润都是0，所以可以认为是一样的。（这对理解初始化至关重要）**

> 解释：

dp\[0\]\[0\]：第一天什么都不做，那么最大利润一定是0；

dp\[0\]\[1\]：第一天第一次持有股票，那么一定是是第一天买入的的股票，也就是-prices\[0\]；

dp\[0\]\[2\]：第一天第一次不持有股票，就是第一天什么都没做，**也可以理解为“股票当天买入当天卖出”**，最大利润就是0；

dp\[0\]\[3\]：第一天第二次持有股票，**可以理解为“这一天已经进行了一次买卖股票”**，接着，又买了一次股票，所以利润就是-prices\[0\]；

dp\[0\]\[4\]：第一天第二次不持有股票，**可以理解为“这一天已经进行了一次买卖股票”**，接着，并没有做任何操作，那么最大利润还是0；

> 初始化：

dp\[0\]\[0\] = 0;//不操作

dp\[0\]\[1\] = -prices\[0\];//第一次持有

dp\[0\]\[2\] = 0;//第一次不持有

dp\[0\]\[3\] = -prices\[0\];//第二次持有

dp\[0\]\[4\] = 0;//第二次不持

## 3.5、解题代码 ##

class Solution {
        public int maxProfit(int[] prices) {
            int[][] dp = new int[prices.length][5];
            //初始化
            dp[0][0] = 0;//不操作
            dp[0][1] = -prices[0];//第一次持有
            dp[0][2] = 0;//第一次不持有
            dp[0][3] = -prices[0];//第二次持有
            dp[0][4] = 0;//第二次不持有
            for(int i = 1; i < prices.length; i++) {
                dp[i][0] = dp[i - 1][0];
                dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
                dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
                dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
                dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
            }
            return dp[prices.length - 1][4];
        }
    }

--------------------

# 四、买股票的最佳时机IV ——>指定次数交易（k次） #

> 题目描述：

![c319b61031394bfe9264a5c76d38df96.png][]

题目来源：[188. 买卖股票的最佳时机 IV][188. _ IV]

## 4.1、分析 ##

本题就是 “买卖股票的最佳时机III” 的升级版，买卖股票的次数由2次变成了k次。

不难看出，本题虽有有了更多的状态，但dp数组的含义，状态转移方程，初始化是一样的；

**因此，如果你理解了 “买卖股票的最佳时机III” 的题解，这道题是可以直接秒杀的；**

## 4.2、解题代码 ##

class Solution {
        public int maxProfit(int k, int[] prices) {
            int ans = 2 * k + 1;
            int[][] dp = new int[prices.length][ans];
            //初始化
            for(int i = 0; i < ans; i++) {
                dp[0][i] = i % 2 == 0 ? 0 : -prices[0];
            }
            //遍历
            for(int i = 1; i < prices.length; i++) {
                dp[i][0] = dp[i - 1][0];
                for(int j = 1; j < ans; j++) {
                    if(j % 2 == 1) { //买入
                        dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i]);
                    } else {
                        dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] + prices[i]);
                    }
                }
            }
            return dp[prices.length - 1][ans - 1];
        }
    }

--------------------

# 五、最佳买卖股票时机含冷冻期 ——>交易到结束（含冷冻期） #

> 题目描述：

![9dbcf4aee36d42fb9d2aef5f7c8bd031.png][]

题目来源：[309. 最佳买卖股票时机含冷冻期][309.]

## 5.1、dp定义 ##

> 分析：

以往的题我们都是拆分成 \[持股，不持股\] 两种状态，本题多了一个冷冻期状态，冷冻期是要求前一天必须为“当天卖出”状态，而我们的“不持股”状态（它表示从某一天卖出开始一直不持股持续到今天，**具体是那一天开始不持股不知道！**）无法准确描述它，因此，**我们需要将“不持股”这个状态拆分成 “冷冻期后的不持股” 和 “当天卖出不持股”这两种状态**。

> dp定义：

dp\[i\]\[0\]：**持股** 时所含的最大利润；

dp\[i\]\[1\]：**冷冻期后的不持股** 时所含的最大利润；

dp\[i\]\[2\]：**当天卖出股票** 时所含的最大利润；

dp\[i\]\[3\]：**冷冻期** 时所含的最大利润；

## 5.2、递推公式 ##

> 分析：

dp\[i\]\[0\]：**持股** 有三种情况：

1.前i - 1天一直持股，今天延续这个状态；2.冷冻期后不持股，然后当天买入股票；3.前一天是冷冻期，今天买入股票。

dp\[i\]\[1\]：**冷冻期后的不持股** 有两种情况：

1.前i - 1天一直是冷冻期后的不持股状态，今天延续这个状态；2.前一天就是冷冻期，今天就是冷冻期后的不持股状态。

dp\[i\]\[2\]：**当天卖出股票** 只有一种情况：

1.前i - 1天持股，今天卖出。

dp\[i\]\[3\]：**冷冻期** 只有一种情况：

1.前一天卖出股票。

> 状态转移方程：

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

dp\[i\]\[1\] = Math.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\];

## 5.3、遍历顺序 ##

由上面的递推公式可以知道，第 i 天的状态是由前i - 1天的状态推导而来，所以是顺序遍历；

## 5.4、初始化 ##

> Ps：这里分析思路和 “买卖股票的最佳时机III的方法是一样的”；

dp\[0\]\[0\] = -prices\[0\];//持股

dp\[0\]\[1\] = 0;//冷冻期后的不持股

dp\[0\]\[2\] = 0;//当天卖出股票

dp\[0\]\[3\] = 0;//冷冻期

## 5.5、解题代码 ##

class Solution {
        public int maxProfit(int[] prices) {
            int len = prices.length;
            int[][] dp = new int[len][4];
            dp[0][0] = -prices[0];//持股
            dp[0][1] = 0;//冷冻期后的不持股
            dp[0][2] = 0;//当天卖出股票
            dp[0][3] = 0;//冷冻期
            for(int i = 1; i < len; i++) {
                dp[i][0] = Math.max(dp[i - 1][0], Math.max(dp[i - 1][1] - prices[i], dp[i - 1][3] - prices[i]));
                dp[i][1] = Math.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];
            }
            return Math.max(dp[len - 1][1], Math.max(dp[len - 1][2], dp[len - 1][3]));
        }
    }

--------------------

# 六、买卖股票的最佳时机含手续费 ——>交易到结束（含手续费） #

> 题目描述：

![957c805563a84e2f9ec9581ec1e02d25.png][]

题目来源：[714. 买卖股票的最佳时机含手续费][714.]

## 6.1、分析 ##

此题可以说是和 “买卖股票的最佳时机II” 几乎一模一样......

唯一的区别就是本题在每次买卖股票完后，都需要减掉一个手续费~

**因此，如果你理解了 “买卖股票的最佳时机II” 的题解，这道题是可以直接秒杀的；**

## 6.2、解题代码 ##

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

--------------------

# 小结 #

你学会怎么买股票了吗？（bushi）

--------------------

![701e0909bb09442bae95082b5f24cdc1.gif][]

[f6344cc181c2453f9002e2e69cd6ed0d.png]: https://img-blog.csdnimg.cn/f6344cc181c2453f9002e2e69cd6ed0d.png
[121.]: https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/
[d843c33ade36452bb0d7bc15f6b26b3a.png]: https://img-blog.csdnimg.cn/d843c33ade36452bb0d7bc15f6b26b3a.png
[122. _ II]: https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/
[8d1f598cdbae44e6a2aa789d1e13f3aa.png]: https://img-blog.csdnimg.cn/8d1f598cdbae44e6a2aa789d1e13f3aa.png
[123. _ III]: https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/
[c319b61031394bfe9264a5c76d38df96.png]: https://img-blog.csdnimg.cn/c319b61031394bfe9264a5c76d38df96.png
[188. _ IV]: https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/
[9dbcf4aee36d42fb9d2aef5f7c8bd031.png]: https://img-blog.csdnimg.cn/9dbcf4aee36d42fb9d2aef5f7c8bd031.png
[309.]: https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/
[957c805563a84e2f9ec9581ec1e02d25.png]: https://img-blog.csdnimg.cn/957c805563a84e2f9ec9581ec1e02d25.png
[714.]: https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/
[701e0909bb09442bae95082b5f24cdc1.gif]: https://img-blog.csdnimg.cn/701e0909bb09442bae95082b5f24cdc1.gif