[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 道股票題都變成模板題了。
所有題目的源程式碼在這裡 。
