道长的算法笔记：状态机模型之股票系列问题
(一) 股票系列问题
所谓的股票问题，是一个动态规划状态机模型的系列问题，这些题目来自于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& 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& 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 与本题的做法也是完全类似的，由于买入与卖出构成一笔交易，又因为只有买入之后才能转到卖出的状态，所以我们可以规定卖出的时候构成一笔交易，然后在此过程添加一个手续费即可，
\[dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee) \] 其余部分保持不变，至此我们已经解决了股票系列的三道题了。
(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& 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& 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& 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\)不持股且不在冷冻期，那它有可能是由前一天不持股且不在冷冻期，或者前一天不持股但在冷冻期转移而来，翻译转为代码即为，
\[dp[i][0] = max(dp[i - 1][0], dp[i - 1][2]) \]如果第\(i\)天持股，那它有可能是由前一天持股，或者前一天不持股但是买入股票转移而来，翻译转为代码即为，
\[dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - x) \]如果第\(i\)天处于冷冻期，那它只有一种可能，即前一天完成了一笔交易(卖出了手上的股票)，翻译转成代码即为，
\[dp[i][2] = dp[i - 1][1] + x \]我们把所有可能的转移过程列出来即可，最终再比较一下第\(n\)天所有不持股且不在冷冻期的状态即可找出最优解。
//
#define MAXN 8000
class Solution {
public:
int dp[MAXN][3];
int maxProfit(vector& 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]);
}
};
(二) 状态机模型
通常动态规划包括状态表示，状态划分与状态转移三个要素，如何进行状态表示与划分通常是一体的，也是分析过程之中最难的一个部分。其中状态表示是指用一个状态来表示某种状态下的一组数据或状态。状态划分是指将问题分成若干个状态，并且每个状态都有若干个属性，通过属性的变化来描述问题的变化。状态转移是指状态的变化过程，即从一个状态转移到另一个状态。
总得来说，动态规划状态机模型是用来描述动态规划算法的一种抽象模型，通过状态的表示、划分、转移来解决问题。划分状态的感觉是需要大量算法题的练习来培养的。