力扣刷题记录（七）动态规划（四）股票系列

水深无声 2022-10-06 15:58 212阅读 0赞

① 题号121. 买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices\[i\] 表示一支给定股票第 i 天的价格。  
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。  
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。  
示例 1：  
输入：\[7,1,5,3,6,4\]  
输出：5  
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。  
示例 2：  
输入：prices = \[7,6,4,3,1\]  
输出：0  
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

解析：  
动规五部曲分析如下  
1.确定dp数组（dp table）以及下标的含义  
dp\[i\]\[0\] 表示第i天持有股票所得最多现金 ，这里可能有同学疑惑，本题中只能买卖一次，持有股票之后哪还有现金呢？  
其实一开始现金是0，那么加入第i天买入股票现金就是 -prices\[i\]， 这是一个负数。  
dp\[i\]\[1\] 表示第i天不持有股票所得最多现金  
注意这里说的是“持有”，“持有”不代表就是当天“买入”！也有可能是昨天就买入了，今天保持持有的状态  
很多同学把“持有”和“买入”没分区分清楚。  
2.确定递推公式  
如果第i天持有股票即dp\[i\]\[0\]， 那么**可以由两个状态推出来**。  
第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即：dp\[i - 1\]\[0\]。  
第i天买入股票，所得现金就是买入今天的股票后所得现金即：-prices\[i\]。  
同样dp\[i\]\[1\]取最大的，dp\[i\]\[1\] = max(dp\[i - 1\]\[1\], prices\[i\] + dp\[i - 1\]\[0\]);  
这样递归公式我们就分析完了。  
3.dp数组如何初始化  
由递推公式 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\]和dp\[0\]\[1\]推导出来。  
那么dp\[0\]\[0\]表示第0天持有股票，此时的持有股票就一定是买入股票了，因为不可能有前一天推出来，所以dp\[0\]\[0\] -= prices\[0\];  
dp\[0\]\[1\]表示第0天不持有股票，不持有股票那么现金就是0，所以dp\[0\]\[1\] = 0;  
4.确定遍历顺序  
从递推公式可以看出dp\[i\]都是有dp\[i - 1\]推导出来的，那么一定是从前向后遍历。  
5.举例推导dp数组  
以示例1，输入：\[7,1,5,3,6,4\]为例，dp数组状态如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70]  
dp\[5\]\[1\]就是最终结果。  
**为什么不是dp\[5\]\[0\]呢？  
因为本题中不持有股票状态所得金钱一定比持有股票状态得到的多！**

答：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][20210614235127479.png]  
② 题号122.买卖股票的最佳时机II  
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。  
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。  
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:  
输入: \[7,1,5,3,6,4\]  
输出: 7  
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4。随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

示例 2:  
输入: \[1,2,3,4,5\]  
输出: 4  
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

示例 3:  
输入: \[7,6,4,3,1\]  
输出: 0  
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

提示：  
1 <= prices.length <= 3 \* 10 ^ 4  
0 <= prices\[i\] <= 10 ^ 4

解析：  
本题和121. 买卖股票的最佳时机的唯一区别本题股票可以买卖多次了（注意只有一只股票，所以再次购买前要出售掉之前的股票）

在动规五部曲中，这个区别主要是体现在递推公式上，其他都和121. 买卖股票的最佳时机一样一样的。

所以我们重点讲一讲递推公式。

这里重申一下dp数组的含义：

dp\[i\]\[0\] 表示第i天持有股票所得现金。  
dp\[i\]\[1\] 表示第i天不持有股票所得最多现金  
如果第i天持有股票即dp\[i\]\[0\]， 那么可以由两个状态推出来

第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即：dp\[i - 1\]\[0\]  
第i天买入股票，所得现金就是昨天不持有股票的所得现金减去 今天的股票价格 即：dp\[i - 1\]\[1\] - prices\[i\]  
注意这里和121. 买卖股票的最佳时机唯一不同的地方，就是推导dp\[i\]\[0\]的时候，第i天买入股票的情况。

在121. 买卖股票的最佳时机中，因为股票全程只能买卖一次，所以如果买入股票，那么第i天持有股票即dp\[i\]\[0\]一定就是 -prices\[i\]。

而本题，因为一只股票可以买卖多次，所以当第i天买入股票的时候，所持有的现金可能有之前买卖过的利润。

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

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

第i-1天就不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金 即：dp\[i - 1\]\[1\]  
第i天卖出股票，所得现金就是按照今天股票佳价格卖出后所得现金即：prices\[i\] + dp\[i - 1\]\[0\]  
注意这里和121. 买卖股票的最佳时机就是一样的逻辑，卖出股票收获利润（可能是负值）天经地义！

答：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][20210615113950954.png]  
③ 题号123.买卖股票的最佳时机III  
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。  
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。  
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1: 输入：prices = \[3,3,5,0,0,3,1,4\] 输出：6 解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3。

示例 2： 输入：prices = \[1,2,3,4,5\] 输出：4 解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4。注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

示例 3： 输入：prices = \[7,6,4,3,1\] 输出：0 解释：在这个情况下, 没有交易完成, 所以最大利润为0。

示例 4： 输入：prices = \[1\] 输出：0

提示：  
1 <= prices.length <= 10^5  
0 <= prices\[i\] <= 10^5

解析：

这道题目相对 121.买卖股票的最佳时机 和 122.买卖股票的最佳时机II 难了不少。  
关键在于至多买卖两次，这意味着可以买卖一次，可以买卖两次，也可以不买卖。

接来下我用动态规划五部曲详细分析一下：

1.确定dp数组以及下标的含义  
一天一共就有五个状态，  
0.没有操作  
1.第一次买入  
2.第一次卖出  
3.第二次买入  
4.第二次卖出  
dp\[i\]\[j\]中 i表示第i天，j为 \[0 - 4\] 五个状态，dp\[i\]\[j\]表示第i天状态j所剩最大现金。

2.确定递推公式  
需要注意：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\]究竟选 dp\[i-1\]\[0\] - prices\[i\]，还是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\])  
同理可推出剩下状态部分：  
dp\[i\]\[3\] = max(dp\[i - 1\]\[3\], dp\[i - 1\]\[2\] - prices\[i\]); dp\[i\]\[4\] = max(dp\[i - 1\]\[4\], dp\[i - 1\]\[3\] + prices\[i\]);

3.dp数组如何初始化  
第0天没有操作，这个最容易想到，就是0，即：dp\[0\]\[0\] = 0;  
第0天做第一次买入的操作，dp\[0\]\[1\] = -prices\[0\];  
第0天做第一次卖出的操作，这个初始值应该是多少呢？  
首先卖出的操作一定是收获利润，整个股票买卖最差情况也就是没有盈利即全程无操作现金为0，  
从递推公式中可以看出每次是取最大值，那么既然是收获利润如果比0还小了就没有必要收获这个利润了。  
所以dp\[0\]\[2\] = 0;  
第0天第二次买入操作，初始值应该是多少呢？应该不少同学疑惑，第一次还没买入呢，怎么初始化第二次买入呢？  
第二次买入依赖于第一次卖出的状态，其实相当于第0天第一次买入了，第一次卖出了，然后在买入一次（第二次买入），那么现在手头上没有现金，只要买入，现金就做相应的减少。  
所以第二次买入操作，初始化为：dp\[0\]\[3\] = -prices\[0\];  
同理第二次卖出初始化dp\[0\]\[4\] = 0;

4.确定遍历顺序  
从递归公式其实已经可以看出，一定是从前向后遍历，因为dp\[i\]，依靠dp\[i - 1\]的数值。

5.举例推导dp数组  
以输入\[1,2,3,4,5\]为例  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 3]  
大家可以看到红色框为最后两次卖出的状态。  
现在最大的时候一定是卖出的状态，而两次卖出的状态现金最大一定是最后一次卖出。  
所以最终最大利润是dp\[4\]\[4\]

答：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 4]  
![在这里插入图片描述][20210615130235391.png]  
![在这里插入图片描述][20210615130252666.png]  
④ 题号188.买卖股票的最佳时机IV  
给定一个整数数组 prices ，它的第 i 个元素 prices\[i\] 是一支给定的股票在第 i 天的价格。  
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。  
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1： 输入：k = 2, prices = \[2,4,1\] 输出：2 解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2。

示例 2： 输入：k = 2, prices = \[3,2,6,5,0,3\] 输出：7 解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4。随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。

提示：  
0 <= k <= 100  
0 <= prices.length <= 1000  
0 <= prices\[i\] <= 1000

答:  
这道题目可以说是动态规划：123.买卖股票的最佳时机III的进阶版，这里要求至多有k次交易。  
动规五部曲，分析如下：  
1.确定dp数组以及下标的含义  
在动态规划：123.买卖股票的最佳时机III中，我是定义了一个二维dp数组，本题其实依然可以用一个二维dp数组。  
使用二维数组 dp\[i\]\[j\] ：第i天的状态为j，所剩下的最大现金是dp\[i\]\[j\]。  
j的状态表示为：  
0 表示不操作  
1 第一次买入  
2 第一次卖出  
3 第二次买入  
4 第二次卖出  
…  
大家应该发现规律了吧 ，除了0以外，偶数就是卖出，奇数就是买入。  
题目要求是至多有K笔交易，那么j的范围就定义为 2 \* k + 1 就可以了。  
所以二维dp数组的C++定义为：  
![在这里插入图片描述][20210615131622489.png]  
2.确定递推公式  
还要强调一下：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\]\[0\]);  
同理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\]\[i\] + prices\[i\], dp\[i\]\[2\])  
同理可以类比剩下的状态，代码如下：  
![在这里插入图片描述][20210615131801490.png]  
本题和动态规划：123.买卖股票的最佳时机III最大的区别就是这里要类比j为奇数是买，偶数是卖剩的状态。  
3.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\]。  
![在这里插入图片描述][20210615131915782.png]  
在初始化的地方同样要类比j为偶数是卖、奇数是买的状态。  
4.确定遍历顺序  
从递归公式其实已经可以看出，一定是从前向后遍历，因为dp\[i\]，依靠dp\[i - 1\]的数值。  
5.举例推导dp数组  
以输入\[1,2,3,4,5\]，k=2为例。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 5]  
最后一次卖出，一定是利润最大的，dp\[prices.size() - 1\]\[2 \* k\]即红色部分就是最后求解。

答：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 6]  
![在这里插入图片描述][20210615133052869.png]  
⑤ 题号309.最佳买卖股票时机含冷冻期  
给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。  
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:  
你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。  
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。  
示例: 输入: \[1,2,3,0,2\] 输出: 3 解释: 对应的交易状态为: \[买入, 卖出, 冷冻期, 买入, 卖出\]

解析：  
1.确定dp数组以及下标的含义  
dp\[i\]\[j\]，第i天状态为j，所剩的最多现金为dp\[i\]\[j\]。  
其实本题很多同学搞的比较懵，是因为出现冷冻期之后，状态其实是比较复杂度，例如今天买入股票、今天卖出股票、今天是冷冻期，都是不能操作股票的。 具体可以区分出如下四个状态：

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

j的状态为：  
0：状态一  
1：状态二  
2：状态三  
3：状态四  
很多题解为什么讲的比较模糊，是因为把这四个状态合并成三个状态了，其实就是把状态二和状态四合并在一起了。  
从代码上来看确实可以合并，但从逻辑上分析合并之后就很难理解了，所以我下面的讲解是按照这四个状态来的，把每一个状态分析清楚。  
注意这里的每一个状态，例如状态一，是买入股票状态并不是说今天已经就买入股票，而是说保存买入股票的状态即：可能是前几天买入的，之后一直没操作，所以保持买入股票的状态。

2.确定递推公式  
达到买入股票状态（状态一）即：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\]，只有一个操作：

操作一：昨天卖出了股票（状态三）  
p\[i\]\[3\] = dp\[i - 1\]\[2\];

综上分析，递推代码如下：  
![在这里插入图片描述][20210615133657595.png]  
3.dp数组如何初始化  
这里主要讨论一下第0天如何初始化。

如果是持有股票状态（状态一）那么：dp\[0\]\[0\] = -prices\[0\]，买入股票所省现金为负数。

保持卖出股票状态（状态二），第0天没有卖出dp\[0\]\[1\]初始化为0就行，

今天卖出了股票（状态三），同样dp\[0\]\[2\]初始化为0，因为最少收益就是0，绝不会是负数。

同理dp\[0\]\[3\]也初始为0。

4.确定遍历顺序  
从递归公式上可以看出，dp\[i\] 依赖于 dp\[i-1\]，所以是从前向后遍历。

5.举例推导dp数组  
以 \[1,2,3,0,2\] 为例，dp数组如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 7]  
最后结果去是 状态二，状态三，和状态四的最大值，不少同学会把状态四忘了，状态四是冷冻期，最后一天如果是冷冻期也可能是最大值。

答：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 8]  
![在这里插入图片描述][20210615135039492.png]  
⑥ 题号714.买卖股票的最佳时机含手续费  
给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；非负整数 fee 代表了交易股票的手续费用。  
你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。  
返回获得利润的最大值。  
注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。  
示例 1: 输入: prices = \[1, 3, 2, 8, 4, 9\], fee = 2 输出: 8  
解释: 能够达到的最大利润: 在此处买入 prices\[0\] = 1 在此处卖出 prices\[3\] = 8 在此处买入 prices\[4\] = 4 在此处卖出 prices\[5\] = 9 总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8.

注意:  
0 < prices.length <= 50000.  
0 < prices\[i\] < 50000.  
0 <= fee < 50000.

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

唯一差别在于递推公式部分，所以本篇也就不按照动规五部曲详细讲解了，主要讲解一下递推公式部分。

这里重申一下dp数组的含义：

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

如果第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);

本题和动态规划：122.买卖股票的最佳时机II的区别就是这里需要多一个减去手续费的操作。

答:  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 9]  
![在这里插入图片描述][20210615140255454.png]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70]: /images/20221005/c46401ddf2f940e5bb29980d6a83c12d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 1]: /images/20221005/dd8995ef7bbe47839b28f4d791e21c45.png
[20210614235127479.png]: /images/20221005/f5f6cfa6f8724c7f8430f608d3317389.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 2]: /images/20221005/7566c522845343dfa4e6953c037d7bb2.png
[20210615113950954.png]: /images/20221005/66058fd93f674e6e9aee4ceb7470c351.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 3]: /images/20221005/ee7492db9a7f4fdab0b1ba91ccaeb991.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 4]: /images/20221005/f511e8e04ea14adb9e6289338f642cb1.png
[20210615130235391.png]: /images/20221005/9672ecc841f4442c8e547c9d01472f91.png
[20210615130252666.png]: /images/20221005/421aac05b36f4226bb9054bd9d24506a.png
[20210615131622489.png]: /images/20221005/999311d92a54421386838ea1fbbc82ac.png
[20210615131801490.png]: /images/20221005/a5414a34b29f45769c287789633e84c6.png
[20210615131915782.png]: /images/20221005/a8c648e5f0fd460ab245d49545c25a85.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 5]: /images/20221005/21a7c54d3e984587ad4d1430918e3601.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 6]: /images/20221005/baff9df5daa143f89a3ae8a04599dfd8.png
[20210615133052869.png]: /images/20221005/353ee674b23741d3bc4812ad1caed9b1.png
[20210615133657595.png]: /images/20221005/6c08b23b2a444746af931a493d4ed02f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 7]: /images/20221005/017f7f14d60147c5a1cefe19e4c028cc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 8]: /images/20221005/a61e555e8b974ea0a1b0de4b8f30414b.png
[20210615135039492.png]: /images/20221005/c186c3b62d75448d81a3b56769b0aa57.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 9]: /images/20221005/884bf5494ef74841a32dd7b4710e2f34.png
[20210615140255454.png]: /images/20221005/66918e218b6e4afab61cd1cfefe9f8a9.png