【动态规划】买卖股票的最佳时机（刷爆股票题）
【动态规划】买卖股票的最佳时机（刷爆股票题）
本文详细讲解了LeetCode中买卖股票系列的六道题目（实际涉及四道），从简单到复杂，逐步深入地介绍了如何使用动态规划解决这类问题。文章将重点放在动态规划的分析步骤上，包括状态表达、转移方程、初始化、填表顺序和返回值，适合有一定编程基础但对动态规划掌握不够深入的读者。
一、前言及No.121热身
本文的题目来自力扣买卖股票的最佳时机系列题目，共六题，如下图：
该系列题考验的核心算法思想是动态规划，难度属于中上，第一题较为简单，这里拿来用作热身。
- 买卖股票的最佳时机 - 力扣（LeetCode）
思路简单来说就是这样：让第i天的价格减去前面最便宜的股价就是当天卖出的最大利润，再和全局的最大利润进行比较即可，代码如下图：
二、No.122 and No.714 关键
- 买卖股票的最佳时机 II - 力扣（LeetCode）
从这题开始难度上升，十分考验我们动态规划的能力。那么在此给出动态规划的核心思路步骤：
- 找到状态表达，创建dp表
- 思考状态转移方程，考虑多种情况
- 根据状态转移方程去初始化dp表
- 考虑填表顺序
- 考虑返回值
这里题目给我们提供一个代表第i天股票价格为prices[i]的数组，我们可以考虑将dp表也设置为一个一维数组，dp[i]表示第i天的最大利润。但是第i天能随便买卖吗？题目限制了只有没有股票的情况下才能买，不能一直买，同时只有持有股票的情况才能卖，这里就能发现其实一天包含两种状态：买入（一天结束后持有股票）和可交易（一天结束后没有持有股票），那么这样我们就可以设置两个dp，一个f代表在第i天结束为买入状态的最大利润，另一个g代表在第i天结束为可交易状态的最大利润。
接下来考虑状态转移方程，第i天结束后是“买入”状态的话，第i-1天是什么状态呢？第i-1天是“买入”状态，即持有股票的话，那么第i天不做任何操作就可以保持买入状态；若第i天是“可交易”状态，那么第i天买入股票（对应利润-prices[i]），第i天结束后就是买入状态，因此第i天结束后是“买入”状态时的最大利润，就是这两者利润经过第i天变化后的较大值，同理g[i]也能得出。
f[i] = max(f[i-1],g[i-1]-prices[i]);
g[i] = max(g[i-1],f[i-1]+prices[i]);
根据上述的状态转移方程，可以发现f[i]和g[i]都依赖于f[i-1]和g[i-1] ，那么初始化时i不能从0开始，（f[-1]代表什么？），i从1开始，所以f[0]和g[0]就需要我们手动去初始化：
f[0] = -prices[0],g[0] = 0;
至于填表顺序，肯定是f[i]和g[i]一起填，然后再i++，因为f[i]和g[i]都依赖于f[i-1]和g[i-1] ，也就是前一个i填的值所以是每个i，两个dp表一起填。
最后是返回值，我们不可能从f表中返回第i天的最大利润，因为如果在第i天结束后还是“买入”状态，也就是还有股票在手，那么一定不是最大利润。因此我们只需要考虑遍历g表即可，又因为g[i]一定不会小于前一个g[i-1]，那么最大利润就是g[n-1]。完整代码如下：
通过上题，那么下一题No.714也是同理，只是在交易时会添加一次手续费，同样的代码稍微修改一下即可：714. 买卖股票的最佳时机含手续费 - 力扣（LeetCode）
三、No.309 拓展
- 买卖股票的最佳时机含冷冻期 - 力扣（LeetCode）
本题其实和上题是差不多的，但是这里又添加了一个“冷冻期”的概念，那么此时的第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];
注意我们这里不使用三个dp表，而是用一个二维dp表，dp[i][j]中i代表第i天，j的0,1,2分别代表买入、可交易、冷冻期三种状态。
其余初始化、填表顺序、返回值就和上述分析类似了，这里不多赘述，给出完整代码：
四、No.123 and No.188 提升
- 买卖股票的最佳时机 III - 力扣（LeetCode）
这题可谓是这类题中最难的了，我们按照之前提到的动态规划分析步骤来试一试。
我们依然可以使用f[i]表示第i天处于买入状态的最大利润，g[i]代表第i天卖出（可交易）状态的最大利润。然而这里还有一个限制：最多购买两次，也就是说交易次数只能是0,1,2次，那么我们就可以将dp表多加一项，改为f[i][j]和g[i][j] ，代表第i天处于买入/卖出状态并且是第j次交易时最大利润，创建数组时j最大为2，这样就保证只有0,1,2三种选项。
接下来进行状态转移方程分析，f[i][j]是第i天结束处于买入状态，仍有股票，那么前一天可以是买入状态，第i天不卖就行，这是f[i-1][j]，因为没卖，所以交易次数一样（卖的时候才进行+1）；还有一种情况，那就是前一天是卖出状态，那么此时第i天花prices[i]的钱买入就行，两者取max即可。
而g[i][j]仍是这样分析，不过却有一个交易次数变换的情况，即前一天是买入状态，第i天卖了，赚了prices[i]的钱，并且j次数是前一天次数+1，那么g[i][j]表达如下：
f[i][j] = max(f[i-1][j],g[i-1][j]-prices[i]);
g[i][j] = max(g[i-1][j],f[i-1][j-1]+prices[i]);
接下来是初始化了，我们发现f和g的第一行是肯定要初始化的，但f的第一列呢？也初始化不好操作。很明显，f中j为-1是不可能的，因此max比较中在j == 0时是没必要比较的，直接等于g[i-1][j]即可，若j>=1了，再取max就能解决了。
g[i][j] = g[i-1][j];
if(j >= 1)
g[i][j] = max(g[i-1][j],f[i-1][j-1]+prices[i]);
接下来第一行如何初始化呢？第0天出现超过0次的交易都是不存在的，那么就要给它们赋值不影响接下来填表的值，我们填表是取max，因此填-无穷即可，用-INT_MAX就行，但这里不一样，max中会有加减操作，这就有可能导致溢出了！那么就选择INT_MAX的一半，也就是0x3f3f3f3f来代替。至于f[0][0]和g[0][0]想必都能明白如何初始化，第1天结束就处于买入f，意味着花prices[i]买了，处于卖出g，其实也就是根本没买，为0即可。
最后一点，返回值，和之前的题一样f表不可能，但利润最多的是g表中的哪一个？交易了两次的吗？看看题目给的用例：
不一定吧？所以我们就遍历g表，选出一个最大值即可完成这道题了！
完整代码如下：
最后，让我们看看No.188吧：188. 买卖股票的最佳时机 IV - 力扣（LeetCode）
这道题和上题No.123是一样的，无非是把两次改为了K次，思路一样，代码也只改了一点：
至此，股票题的六道题（其实也就是四道）完美结束，难度也是不小，不过股票题你要是能做到这里，那你是这个👍