这种动态规划你见过吗——状态机动态规划之股票问题(下) 动态规划算法

这种动态规划你见过吗——状态机动态规划之股票问题(下) 前言
在前面的两篇文章这种动态规划你见过吗——状态机动态规划之股票问题(上)和这种动态规划你见过吗——状态机动态规划之股票问题(中)已经谈了4道和股票问题相关的题目，详细解释了状态机动态规划和他的基本原理和应用方式。在本篇文章当中，会再介绍剩下的两道股票问题，继续深入和学习状态机动态规划。
最佳买卖股票时机含冷冻期
题目

给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例示例1:

输入: prices = [1,2,3,0,2] 输出: 3 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

示例2:

输入: prices = [1] 输出: 0

状态表示数组和状态转移方程和前面的题目一样首先还是需要进行状态的定义和状态转移的分析，在这个问题当中我们用一个二维数组dp[i][j]表示各种不同的状态下的收益，在这个问题当中我们有以下几个状态：

dp[i][0]，表示在遍历到第i支股票的时候没有进行一次买入和卖出。
- 在这个时候没有进行买入和卖出，这个时候的收益和遍历到第i-1支股票的时候没有买入和卖出的情况是一样的，他们的收益都等于0，即dp[i][0] = 0，dp[i - 1][0] = 0。
dp[i][1]，表示在遍历到第i支股票的时候手中含有股票，这个情况可以由三种情况转移过来：
- 在遍历到第i-1支股票的时候手中已经存在股票了，这个时候只需要保持状态，那么在第i支股票的时候的收益和第i-1支股票的收益是相等的，即dp[i][1] = dp[i - 1][1]。
- 第二种情况就是在遍历到第i-1支股票的时候手中不存在股票，那么这个时候要想手中存在股票就需要进行买入了，那么就需要花费prices[i]，那么在遍历到第i支股票的时候收益等于dp[i][1] = dp[i - 1][0] - prices[i]。
- 第三种情况是前一天是处于冷冻期（这里所谈到的冷冻期并不只是前2天卖出，导致的前一天的冷冻期，还有可能是更早之前卖出的，然后保持它的状态，相当于是冷冻期的续期，只不过在续期当中是可以进行买股票的），那么现在是可以进行买入的，即dp[i][1] = dp[i - 1][3] - prices[i]，其中dp[i][3]表示遍历到第i支股票的时候处于冷冻期的收益。
- 综合以上三种情况：
$$ dp[i][1] = max(dp[i - 1][1], max(dp[i - 1][0] - prices[i], dp[i-1][3] - prices[i])) $$
dp[i][2]，表示在第i支股票的时候手中不含有股票，可以转移到这个状态的状态一共有两种：
- 在遍历到第i-1支股票的时候手中本来就不含有股票，那么我们只需要保持状态即可，即dp[i][2] = dp[i - 1][2]。
- 在遍历到第i-1支股票的时候手中含有股票，那么我们需要将这个股票进行售出，即dp[i][2] = dp[i - 1][1] + prices[i]。
- 综合以上两种情况：
$$ dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i]) $$
dp[i][3]，表示在第i支股票的时候是处在冷冻期，这个状态只能由一个状态转移过来，那就是前一天手中没有股票（因为进行卖出了），即dp[i][3] = dp[i][2]。

数组的初始化和遍历顺序根据上面的分析我们可以知道，在遍历到第一支股票的时候如果持有股票的话就需要进行买入，那么买入的状态dp[0][1]的值就等于-prices[0]，卖出的状态收益为0，冷冻期的状态也等于0。根据状态转移方程第i行的数据依赖第i-1行，因此从前往后遍历就行。
最大收益根据上文当中我们设置的状态，我们能够获取的最大的收益为dp[prices.length - 1][2], dp[prices.length - 1][3]两者当中的一个，因为最终我们要想收益最大手中肯定没有股票，而没有股票的状态有上述提到的两个状态。
$$ max(dp[prices.length - 1][2], dp[prices.length - 1][3]) $$
代码

class Solution { public int maxProfit(int[] prices) { // dp[i][0] 表示一次买入和卖出操作都没有这个值始终等于0，可以不用这个状态 // 但是为了完整将这个状态留下来了 // dp[i][1] 表示持有股票 // dp[i][2] 表示不持有股票 // dp[i][3] 卖出操作之后的冷冻期 int[][] dp = new int[prices.length][4]; dp[0][1] = -prices[0]; for (int i = 1; i < prices.length; ++i) { dp[i][1] = Math.max(Math.max(dp[i - 1][1], dp[i - 1][3] - prices[i]), dp[i][0] - prices[i]); // 因为dp[i][0] 始终等于0 因此这里可以直接写 -prices[i] 也行 dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]); dp[i][3] = dp[i - 1][2]; } return Math.max(dp[prices.length - 1][2], dp[prices.length - 1][3]); } }

因为dp[i][0]始终等于0，所以将所有含dp[i][0]的地方都可以删除，因此下面的代码也是正确的。

class Solution { public int maxProfit(int[] prices) { // dp[i][0] 表示一次买入和卖出操作都没有这个值始终等于0，可以不用这个状态 // 但是为了完整将这个状态留下来了 // dp[i][1] 表示持有股票 // dp[i][2] 表示不持有股票 // dp[i][3] 卖出操作之后的冷冻期 int[][] dp = new int[prices.length][4]; dp[0][1] = -prices[0]; for (int i = 1; i < prices.length; ++i) { dp[i][1] = Math.max(Math.max(dp[i - 1][1], dp[i - 1][3] - prices[i]), -prices[i]); dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]); dp[i][3] = dp[i - 1][2]; } return Math.max(dp[prices.length - 1][2], dp[prices.length - 1][3]); } }

数组优化——滚动数组在上面的状态转移方程当中我们始终只使用了两行的数据，因此我们可以只使用一个两行的二维数组，然后进行交替使用（对i求2的余数就可以了）就可以了，代码如下：

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

买卖股票的最佳时机含手续费
题目

给定一个整数数组 prices，其中 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

示例2

输入：prices = [1,3,7,5,10,3], fee = 3 输出：6

状态表示数组和状态转移方程这道题其实和在这种动态规划你见过吗——状态机动态规划之股票问题(上)当中的第二道题很相似，唯一的区别就是这里加上了手续费，其余部分是一模一样。
现在我们来分析一下如何进行状态的转移：

dp[i][0]的状态如何从第i-1的状态转移过来：
- 如果第i-1个状态是手中不存在股票，即dp[i-1][0]，那么第i个状态也没有股票，那么直接是dp[i][0] = dp[i - 1][0]，因为没有进行交易。
- 如果第i-1个状态手中存在股票，即dp[i-1][1]，那么如果想在第i个状态没有股票，那么就需要将股票卖出，那么收益就为dp[i-1][1] + prices[i]，即dp[i][0] = dp[i-1][1] + prices[i]，但是在这个题目当中会有手续费，我们在卖出的时候需要缴纳手续费，那么我们的收益就变成dp[i][0] = dp[i-1][1] + prices[i] -fee。
- 综合上面的两种转移方式可以得到下面的转移方程：
$$ dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i] -fee) $$
dp[i][1]的状态如何进行转移：
- 如果第i-1个状态是手中不存在股票，即dp[i-1][0]，那么我们就需要从第i-1个手中不存在股票的状态进行买入，那么dp[i][0] = dp[i - 1][0] - prices[i]。
- 如果第i-1个状态手中存在股票，即dp[i-1][1]，而第i个状态有股票，因此不需要进行交易，即dp[i][1]=dp[i - 1][1]。
- 综合上面的两种转移方式可以得到下面的转移方程：
$$ dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]); $$
综合上面的两个状态：

$$ \begin{cases}dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i] -fee)\\ dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]); \end{cases} $$
代码

class Solution { public int maxProfit(int[] prices, int fee) { int[][] dp = new int[prices.length][2]; // dp[i][0] 表示不持有股票 // dp[i][1] 表示持有股票 dp[0][1] = -prices[0]; for (int i = 1; i < prices.length; ++i) { dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee); dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]); } return dp[prices.length - 1][0]; } }

数组优化——滚动数组

class Solution { public int maxProfit(int[] prices, int fee) { int[][] dp = new int[2][2]; // dp[i][0] 表示不持有股票 // dp[i][1] 表示持有股票 dp[0][1] = -prices[0]; for (int i = 1; i < prices.length; ++i) { dp[i & 1][0] = Math.max(dp[(i - 1) & 1][0], dp[(i - 1) & 1][1] + prices[i] - fee); dp[i & 1][1] = Math.max(dp[(i - 1) & 1][1], dp[(i - 1) & 1][0] - prices[i]); } return dp[(prices.length - 1) & 1][0]; } }

再优化

class Solution { public int maxProfit(int[] prices, int fee) { int[] dp = new int[2]; // dp[0] 表示不持有股票 // dp[1] 表示持有股票 dp[1] = -prices[0]; for (int i = 1; i < prices.length; ++i) { dp[0] = Math.max(dp[0], dp[1] + prices[i] - fee); dp[1] = Math.max(dp[1], dp[0] - prices[i]); } return dp[0]; } }

上面的代码优化和这种动态规划你见过吗——状态机动态规划之股票问题(中)当中的优化原理是一样的。在下面的代码当中，左边的单行数组dp[0]和dp[1]相当于二维数组当中的dp[i][0]，dp[i][1]，右边的单行数组dp[0]和dp[1]相当于二维数组的dp[i - 1][0]和dp[i - 1][1]。

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

但是我们会发现上面代码的第二行会依赖dp[0]，这个dp[0]是第i-1行的状态，但是dp[0]在第一行已经发生了更新，也就是说dp[0]已经更新到了第i行的状态，那么为什么结果是对的呢？我们可以根据下面三条规则进行分析：

如果dp[0]取的是dp[0]，也就是说dp[0] > dp[1] + prices[i] - fee ，那么dp[0]还是上一行的状态，并不影响dp[1]的结果。
如果dp[0]取的是dp[1] + prices[i] - fee，但是dp[1]取的是上一行的dp[1]那么对结果也没有什么影响。
如果dp[0]取的是dp[1] + prices[i] - fee而且dp[1]取的是dp[0] - prices[i]，那么就有影响了，但是这一加一减其实没有意义，还单纯的需要缴纳手续费，最终dp[0] - prices[i] = dp[1] + prices[i] - fee - prices[i] = dp[1] - fee < dp[1] ，因此这个状态不会被最终的结果取到，被取到的状态肯定都是第i-1行的dp[1]（因为dp[1]更大），也就是说这个状态又会转移到第二条当中，因此对最终的结果没有影响。

总结
在本篇文章当中主要跟大家介绍了最后两道股票问题，第一道题的状态转移还是比较复杂的，可能需要大家仔细进行体会，才能理解，尤其是关于冷冻期的状态的转换可能比较绕。本文当中的第二道题目跟之前的题目非常像，只需要在收益上减去手续费即可。相信看完这三篇文章，做完这六道题目你对状态机动态规划的基本原理已经很了解了，它和传统的动态规划最不一样的就是有很多复杂的状态之间的转换，而且一般的动态规划的题目都是多重循环，但是在状态机动态规划当中是单循环。
更多精彩内容合集可访问项目：https://github.com/Chang-LeHu...
【这种动态规划你见过吗——状态机动态规划之股票问题(下)】关注公众号：一无是处的研究僧，了解更多计算机（Java、Python、计算机系统基础、算法与数据结构）知识。