[leetcode] 股票问题
参考文章:
其实文章 [1] 是文章 [2] 的「二次创作」,建议先阅读 [2] 后再阅读 [1] 。文章 [2] 最大的亮点是使用了状态机图对股票问题进行建模和描述,我觉得是写得很好的文章(因为动态规划最原始的数学模型就是状态机)。
本文通过的题目有:
- 题目[121]:买卖股票的最佳时机
- 题目[122]:买卖股票的最佳时机 II
- 题目[123]:买卖股票的最佳时机 III
- 题目[188]:买卖股票的最佳时机 IV
- 题目[309]:最佳买卖股票时机含冷冻期
- 题目[714]:买卖股票的最佳时机含手续费
预备知识
股票买卖问题的本质是状态穷举。或者说,其实大部分动态规划问题都是状态穷举,只不过是某个状态的计算不是从初始条件开始计算,而是依赖于已经计算过的若干个状态。
股票问题面临的因素有三个:天数 \(N\) 、最大交易次数 \(K\) 、在某天股票的持有状态 \(S(S\in\{0,1\})\) 。
- 状态定义
dp[i][k][s]
表示在第 i
天,最大交易次数为 k
,当前股票持状态为 s
的情况下的最大利润。其中,\(0 \le i \le n-1, 1 \le k \le K, 0 \le s \le 1\) .
显然,股票问题所需的结果是 dp[n-1][K][0]
。为什么不是 dp[n-1][K][1]
呢?因为该状态表示持有股票,最后需要的结果当然是不持有股票的,卖出才具有最大利润。
- 转移方程
假设在第 i
天,最大交易次数为 k
,进行操作后没有持有股票,该状态依赖于:
- 第
i-1
天持有股票,但是第i
天卖出,即dp[i-1][k][1] + price[i]
。 - 第
i-1
天就不持有股票,即dp[i-1][k][0]
。
假设在第 i
天,最大交易次数为 k
,进行操作后持有股票,该状态依赖于:
- 第
i-1
天就持有股票,第i
天什么都不做,即dp[i-1][k][1]
。 - 第
i-1
天不持有股票,第i
天购入股票,即dp[i-1][k-1][0] - price[i]
。因为第i
天需要进行一次交易操作,所以要求前一天的交易次数减一。
所以有:
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + price[i]) if i>=1 and k>=1 dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - price[i]) if i>=1 and k>=1 dp[0][k][0] = 0 if i==0 and k>=1 dp[0][k][1] = -price[0] if i==0 and k>=1
第三个下标只有 0 和 1 ,所以我个人更偏向于将这个三维数组拆分为 2 个二维数组:
dp0[i][k] = max(dp0[i-1][k], dp1[i-1][k] + price[i]) if i>=1 and k>=1 dp1[i][k] = max(dp1[i-1][k], dp0[i-1][k-1] - price[i]) if i>=1 and k>=1
本文就采用 2 个二维数组的形式去解题。
- 边界条件
边界的发生主要发生在变量 i
和 k
上,具体条件是 i == -1
和 k == 0
。
dp[-1][k][0] = 0, dp[-1][k][1] = -INF dp[i][0][0] = 0, dp[i][0][1] = -INF
dp[-1][k][0]
表示允许交易(即 \(k \ge 1\)),但时间未开始(一个形象比喻:股票交易市场未开市),手上未持有股票,利润固然为 0 .
dp[i][0][0]
表示不允许交易,股票市场开市,所以利润为 0 .
dp[-1][k][1]
表示允许交易,股票市场未开市,但手中已持有股票,该状态是不可能的。
dp[i][0][1]
表示不允许交易,股票市场开市,但手中已持有股票,该状态也是不可能的。
因为求解过程中需要取 max
,所以不可能状态以最小值 -INF
表示。
买卖股票的最佳时机
题目[121]:??链接 。
这里 \(K = 1\) ,代入状态转移方程可得:
dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][1][1] + price[i]) if i>=1 dp[i][1][1] = max(dp[i-1][1][1], dp[i-1][0][0] - price[i]) if i>=1
由于 dp[i-1][0][0]
表示不允许交易,且未持有股票,所以为 0 . 因此:
dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][1][1] + price[i]) if i>=1 dp[i][1][1] = max(dp[i-1][1][1], -price[i]) if i>=1
(请注意此处的处理与下面 “买卖股票的最佳时机 Ⅱ” 的区别!)
可以发现,该方程与 K 无关,因此可以进一步简化:
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + price[i]) if i>=1 dp[i][1] = max(dp[i-1][1], -price[i]) if i>=1
dp[i]
只依赖于上一个状态,因此可进行空间优化:
dp0 = max(dp0, dp1 + price[i]) if i>=1 dp1 = max(dp1, -price[i]) if i>=1
初始状态,第 0 天,dp0 = 0
表示在第 0 天未持有股票;dp1 = -price[0]
表示在第 0 天购入股票。
代码如下:
int maxProfit(vector<int> &prices) { if (prices.size() == 0) return 0; int dp0 = 0, dp1 = -prices[0]; for (int x : prices) { dp0 = max(dp0, dp1 + x); dp1 = max(dp1, -x); } return dp0; }
在这篇文章中,还有一个适合新手理解的方法,现在发现二者是一致的,dp1
实际上就是 minval
。
int maxProfit(vector<int> &prices) { int minval = 0x3f3f3f3f; int maxval = 0; for (auto x : prices) { minval = min(x, minval); maxval = max(x - minval, maxval); } return maxval; }
买卖股票的最佳时机 II
题目[122]:买卖股票的最佳时机 II 。
这里允许无限次交易,即 \(K = + \infty\) .
转移方程:
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + price[i]) if i>=1 and k>=1 dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - price[i]) if i>=1 and k>=1
由于 k
是无穷大,因此 k-1
也是无穷大。所以,方程与 k
无关。
dp0[i] = max(dp0[i-1], dp1[i-1] + price[i]) if i>=1 dp1[i] = max(dp1[i-1], dp0[i-1] - price[i]) if i>=1
空间优化:
dp0 = max(dp0, dp1 + price[i]) if i>=1 dp1 = max(dp1, dp0 - price[i]) if i>=1
初始状态:dp0 = 0, dp1 = -price[0]
.
代码:
int maxProfit(vector<int> &prices) { if (prices.size() == 0) return 0; int dp0 = 0, dp1 = -prices[0], t; for (int x : prices) t = dp0, dp0 = max(dp0, dp1 + x), dp1 = max(dp1, t - x); return dp0; }
买卖股票的最佳时机 III
题目[123]:买卖股票的最佳时机 III 。
这里 \(K=2\) ,转移方程:
dp[i][2][0] = max(dp[i-1][2][0], dp[i-1][2][1] + price[i]) if i>=1 dp[i][2][1] = max(dp[i-1][2][1], dp[i-1][1][0] - price[i]) if i>=1
对第三个下标降维,分解为 2 个 DP 数组:
dp0[i][2] = max(dp0[i-1][2], dp1[i-1][2] + price[i]) if i>=1 dp1[i][2] = max(dp1[i-1][2], dp0[i-1][1] - price[i]) if i>=1
我的解法
到这一步,要考虑的是怎么求出 dp0[i-1][1]
?它的含义是只允许一次交易,在第 i 天不持有股票的最大利润。显然这就是第一题 “买卖股票的最佳时机” 所求的。
所以,我们先求出 dp0[n][1]
这个数组,用 vector
记录下来。那么状态方程就变为:
dp0[i][2] = max(dp0[i-1][2], dp1[i-1][2] + price[i]) if i>=1 dp1[i][2] = max(dp1[i-1][2], v[i-1] - price[i]) if i>=1
可以发现,这时候与 k=2
无关(即与第二维下标无关):
dp0[i] = max(dp0[i-1], dp1[i-1] + price[i]) if i>=1 dp1[i] = max(dp1[i-1], v[i-1] - price[i]) if i>=1
空间优化:
dp0 = max(dp0, dp1 + price[i]) if i>=1 dp1 = max(dp1, v[i-1] - price[i]) if i>=1
代码:
int maxProfit3(vector<int> &prices) { if (prices.size() == 0) return 0; vector<int> v(prices.size(), 0); // which is dp0 at above int t = -prices[0]; // which is dp1 at above int n = prices.size(); for (int i = 1; i < n; i++) { v[i] = max(v[i - 1], t + prices[i]); t = max(t, -prices[i]); } int dp0 = 0, dp1 = -prices[0]; for (int i = 1; i < n; i++) { dp0 = max(dp0, dp1 + prices[i]); dp1 = max(dp1, v[i - 1] - prices[i]); } return dp0; }
原作者的解法
\(K=2\) 时的转移方程:
dp[i][2][0] = max(dp[i-1][2][0], dp[i-1][2][1] + price[i]) if i>=1 dp[i][2][1] = max(dp[i-1][2][1], dp[i-1][1][0] - price[i]) if i>=1
进一步对 dp[.][1][.]
进一步展开(实际上就是第一题 “买卖股票的最佳时机” 的转移方程):
dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][1][1] + price[i]) if i>=1 dp[i][1][1] = max(dp[i-1][1][1], dp[i-1][0][0] - price[i]) if i>=1
综合一下:
dp[i][2][0] = max(dp[i-1][2][0], dp[i-1][2][1] + price[i]) if i>=1 dp[i][2][1] = max(dp[i-1][2][1], dp[i-1][1][0] - price[i]) if i>=1 dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][1][1] + price[i]) if i>=1 dp[i][1][1] = max(dp[i-1][1][1], -price[i]) if i>=1
对第二、第三维的下标进行降维:
dp20[i] = max(dp20[i-1], dp21[i-1] + price[i]) if i>=1 dp21[i] = max(dp21[i-1], dp10[i-1] - price[i]) if i>=1 dp10[i] = max(dp10[i-1], dp11[i-1] + price[i]) if i>=1 dp11[i] = max(dp11[i-1], -price[i]) if i>=1
空间优化:
dp20 = max(dp20, dp21 + price[i]) if i>=1 dp21 = max(dp21, dp10 - price[i]) if i>=1 dp10 = max(dp10, dp11 + price[i]) if i>=1 dp11 = max(dp11, dp00 - price[i]) if i>=1
初始状态:dp20=0, dp10=0, dp21=-price[0], dp11=-price[0]
.
代码(Ps:把变量名改为 a,b,c,d
马上 bigger 就高了??):
int maxProfit3(vector<int> &prices) { if (prices.size() == 0) return 0; int dp20 = 0, dp10 = 0, dp21 = -prices[0], dp11 = -prices[0]; for (int x : prices) { dp20 = max(dp20, dp21 + x); dp21 = max(dp21, dp10 - x); dp10 = max(dp10, dp11 + x); dp11 = max(dp11, -x); } return dp20; }
买卖股票的最佳时机 IV
题目[188]:买卖股票的最佳时机 IV 。
这里的 \(K\) 是一个参数。
转移方程:
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + price[i]) if i>=1 and k>=1 dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - price[i]) if i>=1 and k>=1
对第三个下标降维(拆解成 2 个二维数组):
dp0[i][k] = max(dp0[i-1][k], dp1[i-1][k] + price[i]) if i>=1 and k>=1 dp1[i][k] = max(dp1[i-1][k], dp0[i-1][k-1] - price[i]) if i>=1 and k>=1
二维数组形式
超时。当 K = 1000000000, len(prices) = 100000
时,超时。
int maxProfit4(int K, vector<int> &prices) { if (prices.size() == 0) return 0; int n = prices.size(); vector<vector<int>> dp0(n, vector<int>(K + 1, 0)); vector<vector<int>> dp1(n, vector<int>(K + 1, 0)); const int MINVAL = 0x80000000; dp0[0][0] = 0, dp1[0][0] = MINVAL; for (int k = 1; k <= K; k++) dp0[0][k] = 0, dp1[0][k] = -prices[0]; for (int i = 1; i < n; i++) dp0[i][0] = 0, dp1[i][0] = MINVAL; for (int i = 1; i < n; i++) { for (int k = 1; k <= K; k++) { dp0[i][k] = max(dp0[i - 1][k], dp1[i - 1][k] + prices[i]); dp1[i][k] = max(dp1[i - 1][k], dp0[i - 1][k - 1] - prices[i]); } } return dp0[n - 1][K]; }
空间优化:一维数组形式
还是超时了。
方程只出现 i
和 i-1
, 先看空间优化后的结果:
dp0[k] = max(dp0[k], dp1[k] + price[i]) if i>=1 and k>=1 dp1[k] = max(dp1[k], dp0[k-1] - price[i]) if i>=1 and k>=1
值得注意的是,在第 2 行中,dp0[k-1]
是旧 dp0
数组的。
因此这种写法是错误的(对 k 正向扫描,所以当计算 dp1[k]
所用到的 dp0[k-1]
已被更新 ):
for (int i = 1; i < n; i++) for (int k = 1; k <= K; k++) { dp0[k] = max(dp0[k], dp1[k] + prices[i]); dp1[k] = max(dp1[k], dp0[k - 1] - prices[i]); }
代码:
int maxProfit4Version2(int K, vector<int> &prices) { if (prices.size() == 0) return 0; const int minval = 0x80000000; int n = prices.size(); vector<int> dp0(K + 1, 0); vector<int> dp1(K + 1, -prices[0]); dp0[0] = 0, dp1[0] = minval; for (int i = 1; i < n; i++) { vector<int> olddp0(dp0); for (int k = 1; k <= K; k++) { dp0[k] = max(dp0[k], dp1[k] + prices[i]); dp1[k] = max(dp1[k], olddp0[k - 1] - prices[i]); } } return dp0[K]; }
实际上,olddp0
这一临时空间也可以优化(对 k
逆向扫描):
for (int i = 1; i < n; i++) for (int k = K; k >= 1; k--) { dp0[k] = max(dp0[k], dp1[k] + prices[i]); dp1[k] = max(dp1[k], dp0[k - 1] - prices[i]); }
原作者解法
对于 prices
的长度为 \(n\) ,那么最多可以交易的次数为 \(n/2\) . 因此当 \(K \ge n/2\) 时,相当于允许进行无限次交易,这时候就变成第二题 “买卖股票的最佳时机 II” 了。
??这就是面向测试用例编程?!
class Solution { public: int maxProfit(int k, vector<int>& prices) { return maxProfit4Version2(k, prices); } int maxProfit2(vector<int> &prices) { if (prices.size() == 0) return 0; int dp0 = 0, dp1 = -prices[0], t; for (int x : prices) t = dp0, dp0 = max(dp0, dp1 + x), dp1 = max(dp1, t - x); return dp0; } int maxProfit4Version2(int K, vector<int> &prices) { if (prices.size() == 0) return 0; if (K >= prices.size() / 2) return maxProfit2(prices); const int minval = 0x80000000; int n = prices.size(); vector<int> dp0(K + 1, 0); vector<int> dp1(K + 1, -prices[0]); dp0[0] = 0, dp1[0] = minval; for (int i = 1; i < n; i++) { for (int k = K; k >= 1; k--) { dp0[k] = max(dp0[k], dp1[k] + prices[i]); dp1[k] = max(dp1[k], dp0[k - 1] - prices[i]); } } return dp0[K]; } };
最佳买卖股票时机含冷冻期
题目[309]:最佳买卖股票时机含冷冻期 。
此处,\(K = +\infty\) .
消去 k 后的转移方程:
dp0[i] = max(dp0[i-1], dp1[i-1] + price[i]) if i>=1 dp1[i] = max(dp1[i-1], dp0[i-1] - price[i]) if i>=1
本题新增一个要求:卖出股票后,无法在第二天买入股票 (即冷冻期为 1 天)。
而在第二个方程中 dp0[i-1] - price[i]
表示今天在昨天的基础买入股票。
因此需要对第二个方程改进,改为在前天的基础上买入股票:
dp0[i] = max(dp0[i-1], dp1[i-1] + prices[i]) if i>=2 dp1[i] = max(dp1[i-1], dp0[i-2] - prices[i]) if i>=2
代码:
int maxProfit5(vector<int> &prices) { if (prices.size() <= 1) return 0; int n = prices.size(); vector<int> dp0(n, 0), dp1(n, 0); dp0[0] = 0, dp1[0] = -prices[0]; dp0[1] = max(0, prices[1] - prices[0]); dp1[1] = max(-prices[0], -prices[1]); for (int i = 2; i < n; i++) { dp0[i] = max(dp0[i - 1], dp1[i - 1] + prices[i]); dp1[i] = max(dp1[i - 1], dp0[i - 2] - prices[i]); } return dp0.back(); }
空间优化:
int maxProfit5Version2(vector<int> &prices) { if (prices.size() <= 1) return 0; int n = prices.size(); int dp0 = 0, dp1 = -prices[0], predp0 = 0, t; for (int i = 1; i < n; i++) { t = dp0; dp0 = max(dp0, dp1 + prices[i]); dp1 = max(dp1, predp0 - prices[i]); predp0 = t; } return dp0; }
买卖股票的最佳时机含手续费
题目[714]:买卖股票的最佳时机含手续费 。
此处,\(K = + \infty\) .
直接消去 k
后,转移方程为(实际上就是第二题的转移方程):
dp0[i] = max(dp0[i-1], dp1[i-1] + price[i]) if i>=1 dp1[i] = max(dp1[i-1], dp0[i-1] - price[i]) if i>=1
每一次交易,需要交付 fee 个单位的利润作为手续费。
假如在卖出股票的时候交手续费,那么有:
dp0[i] = max(dp0[i-1], dp1[i-1] + price[i] - fee) if i>=1 dp1[i] = max(dp1[i-1], dp0[i-1] - price[i]) if i>=1
假如在购入股票的时候交手续费,那么有:
dp0[i] = max(dp0[i-1], dp1[i-1] + price[i]) if i>=1 dp1[i] = max(dp1[i-1], dp0[i-1] - price[i] - fee) if i>=1
PS: 还可以优化空间,就不多写,上面已经写过不少了。
出售股票时交手续费:
int maxProfit6(vector<int> &prices, int fee) { if (prices.size() == 0) return 0; int dp0 = 0, dp1 = -prices[0], t; for (int x : prices) { t = dp0; dp0 = max(dp0, dp1 + x - fee); dp1 = max(dp1, t - x); } return dp0; }
买入股票时交手续费:
int maxProfit6(vector<int> &prices, int fee) { if (prices.size() == 0) return 0; int dp0 = 0, dp1 = -prices[0] - fee, t; for (int x : prices) { t = dp0; dp0 = max(dp0, dp1 + x); dp1 = max(dp1, t - x - fee); } return dp0; }
总结
原作者 fun4leetcode
实在太厉害了!????看完之后,6 道股票题都变成模板题了。
所有题目的源代码在这里 。