(一) 股票系列问题
所谓的股票问题，是一个动态规划状态机模型的系列问题，这些题目来自于LeetCode社区，这些问题非常经典，能够帮助我们理解动态规划的本质，这些问题大多初看之下会令人感觉无从下手，但是一旦掌握相应的方法划分状态之后，很快即可举一反三的写出相应的代码。
- 股票系列问题合集
- LC121 买卖股票的最佳时机
- LC122 买卖股票的最佳时机 II
- LC123 买卖股票的最佳时机 III
- LC188 买卖股票的最佳时机 IV
- LC309 最佳买卖股票时机含冷冻期
- LC714 买卖股票的最佳时机含手续费
(1.1) 股票买卖(交易一次)
首先来看 LC121，首先根据持股与不持股的状态，我们可以写出两个状态，然后我们按照「动作」画出状态转移的连边，比如买入会使不持股转为持股，卖出会使持股转为不持股，什么也不做则保持当前状态不变。
我们根据画出的状态转移图翻译代码即可，由于涉及两个状态，我们使用 (dp[i][0]) 代表第 i 天不持股，(dp[i][1]) 代表第 i 天持股的状态，同时为了代码编写方便，我们虚设一个第零天，将其初始化为零，这种做法的主目的是避免遍历 (dp) 数组过程之中对于下标的特殊处理。
初始化 (dp[0][0] = 0)，其它所有状态设为负无穷，以此表示仅能以第零天作为所有状态转移的起点。
由于仅能交易一次，当从不持股的状态转为持股状态的时候，此时必然是第一次买入，此时花销即为当日股票价格 (-x)，或者也可以写成 (dp[0][0]-x)，具体实现详见下列代码。
#define MAXN 100005 class Solution { public: int dp[MAXN][2]; int maxProfit(vector<int>& prices) { int n = prices.size(); memset(dp, 0xcf, sizeof(dp)); dp[0][0] = 0; for(int i = 1; i <= prices.size(); i++){ int x = prices[i - 1]; dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + x); dp[i][1] = max(dp[i - 1][1], -x); } return dp[n][0]; } };
(1.2) 股票买卖(次数不限)
再看股票系列的LC122，与仅交易一次的股票题非常类似，如果允许多次买卖则为前一天最大收益减去买入当日股票的开销，也即是说， (dp[i][0]-x)，状态转移图 LC121 基本一致。
#define MANX 300005 class Solution { public: int dp[MANX][2]; int maxProfit(vector<int>& prices) { int n = prices.size(); memset(dp, 0xcf, sizeof(dp)); dp[0][0] = 0; for(int i = 1; i <= n; i++){ int x = prices[i - 1]; dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + x); dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - x); } return dp[n][0]; } }; 股票系列的 LC714 与本题的做法也是完全类似的，由于买入与卖出构成一笔交易，又因为只有买入之后才能转到卖出的状态，所以我们可以规定卖出的时候构成一笔交易，然后在此过程添加一个手续费即可，
其余部分保持不变，至此我们已经解决了股票系列的三道题了。
(1.3) 股票买卖(两次交易)
我们使用 (A) 代表持股，(B) 代表不持股，然后使用 (0/1/2) 分别代表已经交易的次数，那么根据乘法原理，我们需要建立六个状态，然后再根据动作关系画出状态之间的转移关系。我们规定每一次卖出算是一交易，类似于处理手续费的时候，我们之中只考虑卖出的时候计算手续费一样。
根据买卖关系画出之后状态转移图之后，会发现状态 (A2)(持股且已经交易两次)这个状态是多余的，因而持股意味着手里存在买入的股票，买入股票是需要花钱的，故其必非最优解。
// 我们使用0/1/2/3/4/5分别表示上面B0,A0,B1,A1,B2状态 #define MAXN 400005 class Solution { public: int dp[MAXN][5]; int maxProfit(vector<int>& prices) { int n = prices.size(); memset(dp, 0xcf, sizeof(dp)); dp[0][0] = 0; for(int i = 1; i <= n; i++){ int x = prices[i - 1]; dp[i][0] = dp[i - 1][0]; dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - x); dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + x); dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - x); dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + x); } return max({dp[n][0], dp[n][2], dp[n][4]}); } };
或者我们可以解耦上述的状态，我们把交易次数单独设为数组的一个维度，持股与否单独设为设为数组的一个维度，然后再用枚举的方式访问这些状态，对其按照状态转移图中的关系进行转移即可。 这个方法能够推广至多笔交易的情况。
#define MANX 100005 class Solution { public: int dp[MANX][3][2]; int maxProfit(vector<int>& prices) { int n = prices.size(); memset(dp, 0xcf, sizeof(dp)); dp[0][0][0] = 0; // 第零天, 完成了零笔交易, 不持股 for(int i = 1; i <= n; i++){ int x = prices[i - 1]; for(int j = 0; j <= 2; j++){ if(j == 0){ dp[i][j][0] = dp[i - 1][j][0]; }else{ dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j - 1][1] + x); } dp[i][j][1] = max(dp[i - 1][j][1], dp[i - 1][j][0] - x); } } int ans = 0; for(int i = 0; i <= 2; i++){ ans = max(ans, dp[n][i][0]); } return ans; } };
(1.4) 股票买卖(交易多次)
状态转移图与两次交易的股票买卖是完全类似的，如果允许交易次数等于 (k)，那么再按一维数组的方法去给状态编号，然后设计状态转移关系便不现实了。此时我们要把状态解耦，已经交易的次数单独设置一维，是否持股单独一维。
我们使用 (dp[i][k][0]) 代表第(i)天、已经交易次数(k)、不持股，(dp[i][k][1]) 代表第(i)天、已经交易次数(k)、持股。如果题目引入更多复杂的状态，我们也能以此类推，每多一个状态便多开一维数组。
#define MAXN 1005 class Solution { public: int dp[MAXN][105][2]; int maxProfit(int k, vector<int>& prices) { int n = prices.size(); memset(dp, 0xcf, sizeof(dp)); dp[0][0][0] = 0; for(int i = 1; i <= n; i++){ int x = prices[i - 1]; for(int j = 0; j <= k; j++){ if(j == 0){ dp[i][j][0] = dp[i - 1][j][0]; }else{ dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j - 1][1] + x); } dp[i][j][1] = max(dp[i - 1][j][1], dp[i - 1][j][0] - x); } } int ans = 0; for(int i = 0; i <= k; i++){ ans = max(ans, dp[n][i][0]); } return ans; } };
(1.4) 股票买卖(带有冷冻期)
类似的，我们需要考虑当前状态是否处于冷冻期，是否持股，根据乘法原理，我们需要划分四个状态，但是我发现持股但处于冷冻期是一个不可能存在的状态，所以实际只有三个状态。
我们只要看图，将其翻译转为代码即可，首先我要给这些状态编个号，我们使用 (0) 代表不持股且不在冷冻期, (1) 代表持股，(2) 代表不持股且处于冷冻期。如果第(i)不持股且不在冷冻期，那它有可能是由前一天不持股且不在冷冻期，或者前一天不持股但在冷冻期转移而来，翻译转为代码即为，
如果第(i)天持股，那它有可能是由前一天持股，或者前一天不持股但是买入股票转移而来，翻译转为代码即为，
如果第(i)天处于冷冻期，那它只有一种可能，即前一天完成了一笔交易(卖出了手上的股票)，翻译转成代码即为，
我们把所有可能的转移过程列出来即可，最终再比较一下第(n)天所有不持股且不在冷冻期的状态即可找出最优解。
// #define MAXN 8000 class Solution { public: int dp[MAXN][3]; int maxProfit(vector<int>& prices) memset(dp, 0xcf, sizeof(dp)); dp[0][0] = 0; int n = prices.size(); for(int i = 1; i <= n; i++){ int x = prices[i - 1]; dp[i][0] = max(dp[i - 1][0], dp[i - 1][2]); dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - x); dp[i][2] = dp[i - 1][1] + x; } return max(dp[n][0], dp[n][2]); } };
(二) 状态机模型
通常动态规划包括状态表示，状态划分与状态转移三个要素，如何进行状态表示与划分通常是一体的，也是分析过程之中最难的一个部分。其中状态表示是指用一个状态来表示某种状态下的一组数据或状态。状态划分是指将问题分成若干个状态，并且每个状态都有若干个属性，通过属性的变化来描述问题的变化。状态转移是指状态的变化过程，即从一个状态转移到另一个状态。
总得来说，动态规划状态机模型是用来描述动态规划算法的一种抽象模型，通过状态的表示、划分、转移来解决问题。划分状态的感觉是需要大量算法题的练习来培养的。
支持作者
