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

时间:2023-01-06 21:05:49

(一) 股票系列问题

 所谓的股票问题,是一个动态规划状态机模型的系列问题,这些题目来自于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]);
    }
};

(二) 状态机模型

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

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

支持作者

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