道长的算法笔记：状态机模型之股票系列问题

(一) 股票系列问题

　所谓的股票问题，是一个动态规划状态机模型的系列问题，这些题目来自于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 与本题的做法也是完全类似的，由于买入与卖出构成一笔交易，又因为只有买入之后才能转到卖出的状态，所以我们可以规定卖出的时候构成一笔交易，然后在此过程添加一个手续费即可，

\[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<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\)不持股且不在冷冻期，那它有可能是由前一天不持股且不在冷冻期，或者前一天不持股但在冷冻期转移而来，翻译转为代码即为，

\[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<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]);
    }
};

(二) 状态机模型

　通常动态规划包括状态表示，状态划分与状态转移三个要素，如何进行状态表示与划分通常是一体的，也是分析过程之中最难的一个部分。其中状态表示是指用一个状态来表示某种状态下的一组数据或状态。状态划分是指将问题分成若干个状态，并且每个状态都有若干个属性，通过属性的变化来描述问题的变化。状态转移是指状态的变化过程，即从一个状态转移到另一个状态。

　总得来说，动态规划状态机模型是用来描述动态规划算法的一种抽象模型，通过状态的表示、划分、转移来解决问题。划分状态的感觉是需要大量算法题的练习来培养的。

支持作者