目录

前言

一、买卖股票的最佳时机 ——>指定次数交易（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次）

题目描述：

题目来源：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 ——>交易到结束

题目描述：

 题目来源：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次）

题目描述：

题目来源：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次）

题目描述：

题目来源：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];}
}

---

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

题目描述：

题目来源：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]));}
}

---

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

题目描述：

题目来源：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）

---