Leetcode|有限状态自动机团灭买卖股票6道题

本文主要是介绍Leetcode|有限状态自动机团灭买卖股票6道题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

0 前言及问题描述

大三编译原理中的确定有限状态自动机DFA，其实是动态规划中的一大杀器。我们知道，动态规划中最难之一的是写出状态转移方程，而导致状态转移的根本正是题目中的选择，因此，只要我们根据选择列表绘出对应状态的有限自动机，即可找到写出状态转移方程的突破口。感谢labuladong公众号的讲解，以下以力扣的买卖股票问题为例，加以总结

1 有限状态自动机的使用

我们根据题目列出以下四个状态，但只有前三个状态的上下界是题目已知的，第四个状态的上界未知，因此我们只能使用前三个状态作为dp数组索引，将第四个状态作为值

【状态】：①天数（数组索引i）；②剩余交易次数k；③是否持有股票1或0；④累计利润（待求）

【选择】：①在第i天买股票；②在第i天卖股票；③第i天不交易

由于选择决定状态如何转移，因此，我们从选择入手，找到不同选择会改变的状态为②剩余交易次数k和③是否持有股票1或0，这里，画出选择和状态③之间有限状态自动机

有了状态自动机，我们即可快速找到状态转移关系，设选择列表为 A = { b u y , s e l l , r e s t } A = \{buy, sell, rest\} A={buy,sell,rest}，状态集为 S = { s 0 , s 1 } S = \{s_0, s_1\} S={s0​,s1​}，每个状态的价值(累计利润)为$V(s)$，每个状态执行某个动作后的价值为$Q(s,a)$，则有
V ( s 0 ) = max ⁡ { Q ( s 0 , r e s t ) , Q ( s 1 , s e l l ) } V ( s 1 ) = max ⁡ { Q ( s 1 , r e s t ) , Q ( s 0 , b u y ) } V(s_0) = \max \{Q(s_0, rest), Q(s_1, sell)\} \\ V(s_1) = \max \{Q(s_1, rest),Q(s_0, buy)\} V(s0​)=max{Q(s0​,rest),Q(s1​,sell)}V(s1​)=max{Q(s1​,rest),Q(s0​,buy)}

2 股票问题框架

有了以上思路整出框架啦

2.1初始化

1. 通用初始化全为0
2. 不符合条件的状态对应值为负无穷（①第0天持有股票的状态 + ②无剩余股票交易次数时还持有股票）

dp[0][1...K][1] = INT_MIN;
dp[1...i][0][1] = INT_MIN;

2.3 总体框架

【dp数组含义】第i天剩余交易数为k下持有股票的累计最大收益为dp[i][k][1]，未持有股票为dp[i][k][0]

class Solution {
public:int maxProfit(vector<int>& prices, int K) {int size = prices.size();// dp数组含义：第i天剩余交易数为k下持有股票的累计最大收益为dp[i][k][1]，未持有股票为dp[i][k][0]vector<vector<vector<int>>> dp(size + 1, vector<vector<int>> (K + 1, vector<int> (2, 0)));// 边界初始化dp[0][1...K][1] = INT_MIN;dp[1...i][0][1] = INT_MIN;for (int i = 1; i <= size; i++) for (int k = 1; k <= K; k++) {dp[i][k][0] = max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i - 1]);dp[i][k][1] = max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i - 1]);}return dp[size][K][0];}
};

① 买卖股票的最佳时机（$k=1$）

1.1 股票三维DP框架照搬（885ms）

class Solution {
public:int maxProfit(vector<int>& prices) {int size = prices.size();vector<vector<vector<int>>> dp(size + 1, vector<vector<int>> (2, vector<int> (2, 0)));dp[0][1][1] = INT_MIN;for (int i = 1; i <= size; i++) {for (int k = 1; k <= 1; k++) {dp[i][k][0] = max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i - 1]);dp[i][k][1] = max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i - 1]);}}return dp[size][1][0];}
};

由于第二个for循环只有1次，进一步可修改为

for (int i = 1; i <= size; i++) {dp[i][1][0] = max(dp[i - 1][1][0], dp[i - 1][1][1] + prices[i - 1]);dp[i][1][1] = max(dp[i - 1][1][1], dp[i - 1][0][0] - prices[i - 1]);
}

由于状态转移方程中没有改变dp[i][0][0]的量，因此有dp[i][0][0] == 0，第二个状态转移可简写为

dp[i][1][1] = max(dp[i - 1][1][1], - prices[i - 1]);

最终得到

class Solution {
public:int maxProfit(vector<int>& prices) {int size = prices.size();vector<vector<vector<int>>> dp(size + 1, vector<vector<int>> (2, vector<int> (2, 0)));dp[0][1][1] = INT_MIN;for (int i = 1; i <= size; i++) {dp[i][1][0] = max(dp[i - 1][1][0], dp[i - 1][1][1] + prices[i - 1]);dp[i][1][1] = max(dp[i - 1][1][1], - prices[i - 1]);}return dp[size][1][0];}
};

1.2 优化为二维DP（336ms）

既然k == 1，因此可直接降维到二维

class Solution {
public:int maxProfit(vector<int>& prices) {int size = prices.size();vector<vector<int>> dp(size + 1, vector<int> (2, 0));dp[0][1] = INT_MIN;for (int i = 1; i <= size; i++) {dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i - 1]);dp[i][1] = max(dp[i - 1][1], - prices[i - 1]);}return dp[size][0];}
};

1.3 空间复杂度优化为$O(1)$（136ms）

进一步观察，可以约掉[i - 1]项

class Solution {
public:int maxProfit(vector<int>& prices) {int size = prices.size();int dp_i_0 = 0, dp_i_1 = INT_MIN;for (int i = 0; i < size; i++) {dp_i_0 = max(dp_i_0, dp_i_1 + prices[i]);dp_i_1 = max(dp_i_1, - prices[i]);}return dp_i_0;}
};

② 买卖股票的最佳时机II（$k=\infty$）

2.1 股票DP框架照搬（12ms）

由于$k=\infty$，因此可以认为$k\to k-1$

dp[i][k][1] = max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i - 1]);= max(dp[i - 1][k][1], dp[i - 1][k][0] - prices[i - 1]);
p[i][k][0] = max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i - 1]);

因此，既然全是k，可直接把三维DP降维到二维DP

class Solution {
public:int maxProfit(vector<int>& prices) {int size = prices.size();vector<vector<int>> dp(size + 1, vector<int>(2, 0));dp[0][1] = INT_MIN;for (int i = 1; i <= size; i++) {dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i - 1]);dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i - 1]);}return dp[size][0];}
};

2.2 空间复杂度优化为$O(1)$（0ms）

其中dp[i][0]作为第二步计算前会被更新覆盖，找个零时变量存储一下就能解决

class Solution {
public:int maxProfit(vector<int>& prices) {int size = prices.size();int dp_i_0 = 0, dp_i_1 = INT_MIN;for (int i = 1; i <= size; i++) {int tmp = dp_i_0;dp_i_0 = max(dp_i_0, dp_i_1 + prices[i - 1]);dp_i_1 = max(dp_i_1, tmp - prices[i - 1]);}return dp_i_0;}
};

③ 最佳买卖股票时机含冷冻期（$k=\infty$ + 冷冻期）

3.1 股票DP框架照搬（8ms）

• 由于$k=\infty$，因此可以认为$k\to k-1$
• 而多加了1天冷冻期，则对于当天的持有，由①前一天持有；②至少2天前卖出导致未持有，然后今天买入；两者状态转移而成

【状态转移】

dp[i][0]= max(dp[i - 1][0], dp[i - 1][1] + prices[i - 1]);   // 当天未持有
dp[i][1] = max(dp[i - 1][1], dp[i - 2][0] - prices[i - 1]);  // 当天持有

写完状态转移后，由于有dp[i - 2]，所以要对dp[0][1], dp[1][0], dp[1][1]初始化，完整代码如下

class Solution {
public:int maxProfit(vector<int>& prices) {int size = prices.size();vector<vector<int>> dp(size + 1, vector<int>(2, 0));dp[0][1] = INT_MIN;dp[1][0] = 0;dp[1][1] = - prices[0];for (int i = 2; i <= size; i++) {dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i - 1]);dp[i][1] = max(dp[i - 1][1], dp[i - 2][0] - prices[i - 1]);}return dp[size][0];}
};

3.2 空间复杂度优化为$O(1)$（0ms）

class Solution {
public:int maxProfit(vector<int>& prices) {int size = prices.size();int dp_i_0 = 0, pre_dp_i_0 = 0, dp_i_1 = - prices[0];for (int i = 2; i <= size; i++) {int tmp = dp_i_0;dp_i_0 = max(dp_i_0, dp_i_1 + prices[i - 1]);dp_i_1 = max(dp_i_1, pre_dp_i_0 - prices[i - 1]);pre_dp_i_0 = tmp;}return dp_i_0;}
};

④ 买卖股票的最佳时机含手续费（$k=\infty$ + 手续费）

4.1 股票DP框架照搬（232ms）

• 由于$k=\infty$，因此可以认为$k\to k-1$
• 而每交易完1笔，即卖出当前股票后，需要支付一个常数小费

【状态转移】

dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i - 1] - fee);  // 当天未持有
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i - 1]);        // 当天持有

写完状态转移后，由于有dp[i - 1]，所以要对dp[0][1]初始化，完整代码如下

class Solution {
public:int maxProfit(vector<int>& prices, int fee) {int size = prices.size();vector<vector<int>> dp(size + 1, vector<int>(2, 0));dp[0][1] = INT_MIN;for (int i = 1; i <= size; i++) {if (prices[i - 1] < fee) dp[i][0] = dp[i - 1][0];else dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i - 1] - fee);dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i - 1]);}return dp[size][0];}
};

4.2 空间复杂度优化为$O(1)$（84ms，99%beat）

class Solution {
public:int maxProfit(vector<int>& prices, int fee) {int size = prices.size();int dp_i_0 = 0, dp_i_1 = INT_MIN;for (int i = 0; i < size; i++) {if (prices[i] >= fee) dp_i_0 = max(dp_i_0, dp_i_1 + prices[i] - fee);dp_i_1 = max(dp_i_1, dp_i_0 - prices[i]);}return dp_i_0;}
};

⑤ 买卖股票的最佳时机 III（$k=2$）

5.1 股票三维DP框架照搬（904ms）

• 由于$k=2$，因此可直接套用三维有限状态机框架

【状态转移】

dp[i][k][0] = max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i - 1]);      // 当天未持有
dp[i][k][1] = max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i - 1]);  // 当天持有

写完状态转移后，需要对dp[0][k][1]初始化负无穷，完整代码如下

class Solution {
public:int maxProfit(vector<int>& prices) {int size = prices.size(), K = 2;vector<vector<vector<int>>> dp(size + 1, vector<vector<int>>(K + 1, vector<int>(2, 0)));// for (int k = 0; k <= K; k++) dp[0][k][1] = INT_MIN;dp[0][1][1] = INT_MIN;dp[0][2][1] = INT_MIN;for (int i = 1; i <= size; i++) for (int k = 1; k <= K; k++) {dp[i][k][0] = max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i - 1]);dp[i][k][1] = max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i - 1]);}return dp[size][K][0];}
};

5.2 优化为二维DP（176ms，81%beat）

我们发现状态转移的前一个状态都是dp[i - 1]..，因此可直接降维到二维

class Solution {
public:int maxProfit(vector<int>& prices) {int size = prices.size(), K = 2;vector<vector<int>> dp(K + 1, vector<int>(2, 0));// for (int k = 1; k <= K; k++) dp[k][1] = INT_MIN;dp[1][1] = INT_MIN;dp[2][1] = INT_MIN;for (int i = 0; i < size; i++) for (int k = 1; k <= K; k++) {dp[k][0] = max(dp[k][0], dp[k][1] + prices[i]);dp[k][1] = max(dp[k][1], dp[k - 1][0] - prices[i]);}return dp[K][0];}
};

5.3 空间复杂度优化为$O(1)$（132ms，98%beat）

在优化之前，我们先把第二个关于k的for循环展开得到

for (int i = 0; i < size; i++) {dp[1][0] = max(dp[1][0], dp[1][1] + prices[i]);dp[1][1] = max(dp[1][1], dp[0][0] - prices[i]);dp[2][0] = max(dp[2][0], dp[2][1] + prices[i]);dp[2][1] = max(dp[2][1], dp[1][0] - prices[i]);
}

不难发现，dp[k]和dp[k-1]只有最后一行第二项才有依赖，其余没有。而不同i下的dp[k]和dp[k]均有依赖

所以不能简写成2行，而需要把k展开写，针对dp[1][1]和dp[2][1]依然单独初始化负无穷，其余全部初始化为0

class Solution {
public:int maxProfit(vector<int>& prices) {int size = prices.size(), K = 2;int dp_0_0 = 0, dp_1_0 = 0, dp_2_0 = 0, dp_1_1 = INT_MIN, dp_2_1 = INT_MIN;for (int i = 0; i < size; i++) {dp_1_0 = max(dp_1_0, dp_1_1 + prices[i]);dp_1_1 = max(dp_1_1, dp_0_0 - prices[i]);dp_2_0 = max(dp_2_0, dp_2_1 + prices[i]);dp_2_1 = max(dp_2_1, dp_1_0 - prices[i]);}return dp_2_0;}
};

⑥ 买卖股票的最佳时机 IV（$k=K$）

6.1 股票三维DP框架照搬（40ms，14%beat）

• 由于$k=K$，因此可直接套用三维有限状态机框架

【状态转移】

dp[i][K][0] = max(dp[i - 1][K][0], dp[i - 1][K][1] + prices[i - 1]);      // 当天未持有
dp[i][K][1] = max(dp[i - 1][K][1], dp[i - 1][K - 1][0] - prices[i - 1]);  // 当天持有

写完状态转移后，需要对dp[0][k][1]初始化负无穷，完整代码如下

class Solution {
public:int maxProfit(int k, vector<int>& prices) {int size = prices.size();vector<vector<vector<int>>> dp(size + 1, vector<vector<int>>(k + 1, vector<int>(2, 0)));for (int j = 0; j <= k; j++) dp[0][j][1] = INT_MIN;for (int i = 1; i <= size; i++)for (int K = 1; K <= k; K++) {dp[i][K][0] = max(dp[i - 1][K][0], dp[i - 1][K][1] + prices[i - 1]);dp[i][K][1] = max(dp[i - 1][K][1], dp[i - 1][K - 1][0] - prices[i - 1]);}return dp[size][k][0];}
};

6.2 优化为二维DP（0ms，100%beat）

我们发现状态转移的前一个状态都是dp[i - 1]..，因此可直接降维到二维

class Solution {
public:int maxProfit(int k, vector<int>& prices) {int size = prices.size();vector<vector<int>> dp(k + 1, vector<int>(2, 0));for (int j = 0; j <= k; j++) dp[j][1] = INT_MIN;for (int i = 0; i < size; i++)for (int K = 1; K <= k; K++) {dp[K][0] = max(dp[K][0], dp[K][1] + prices[i]);dp[K][1] = max(dp[K][1], dp[K - 1][0] - prices[i]);}return dp[k][0];}
};

6.3 解决$k\to \infty$可能导致的超内存现象

对于Leetcode的测试用例，都是很小的，但实际大厂笔试时，可能会出$k\to \infty$的案例从而导致潜在超内存现象

解决方法很简单，由于消耗1次k最少需要2天，即当k > size / 2时则判定属于$k\to \infty$情况，此时直接调用之前的$O(1)$方法即可，代码如下

class Solution {
public:int maxProfit(int k, vector<int>& prices) {int size = prices.size();// 1.消耗1次k最少需要2天，因此可判断若k是+infty则更简单, O(1)if (k > size / 2) {int dp_0 = 0, dp_1 = INT_MIN;for (int i = 0; i < size; i++) {dp_0 = max(dp_0, dp_1 + prices[i]);dp_1 = max(dp_1, dp_0 - prices[i]);}return dp_0;}// 2.k是常数vector<vector<int>> dp(k + 1, vector<int>(2, 0));for (int j = 0; j <= k; j++) dp[j][1] = INT_MIN;for (int i = 0; i < size; i++)for (int K = 1; K <= k; K++) {dp[K][0] = max(dp[K][0], dp[K][1] + prices[i]);dp[K][1] = max(dp[K][1], dp[K - 1][0] - prices[i]);}return dp[k][0];}
};

至此，完结撒花啦✿✿ヽ(°▽°)ノ✿

参考文献

[1] labuladong. LeetCode 股票买卖问题

这篇关于Leetcode|有限状态自动机团灭买卖股票6道题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---