該文為引用翻譯leetcode一總結(jié)帖
本文為Leetcode上一系列股票買賣最大利潤問題匯總，題目如下：
121. Best Time to Buy and Sell Stock
122. Best Time to Buy and Sell Stock II
123. Best Time to Buy and Sell Stock III
188. Best Time to Buy and Sell Stock IV
309. Best Time to Buy and Sell Stock with Cooldown
714. Best Time to Buy and Sell Stock with Transaction Fee
以上每個問題，其實都有各自解法。而本文將總結(jié)上述所有問題的通用解法。
1. 一般情況
首先考慮這樣一個問題：
給定一個每日股價的數(shù)組，怎么樣獲得最大利潤？
多數(shù)人可能想到的是：“重點在于哪天買進哪天賣出，以及我們能交易幾次”。但其實還有個隱藏的重要因素。
首先，我們先定義一下變量：
price是股價數(shù)組， 長度為n,
i表示第i天（0到n-1),
k表示允許幾次交易（交易量）。
T[i][k]表示第i天在最多k次交易下最大的利潤。
所以很明顯的，基礎(chǔ)情況就是：T[-1][k] = T[i][0] = 0 表示0股價或0交易就是0利潤（因為第一天是i=0，所以第-1天就是沒有股價）。
所以第i天交易就可以轉(zhuǎn)化成子問題：T[i-1][k], T[i][k-1], T[i-1][k-1], ... 然后就可以遞歸求解。 所以具體該怎么做呢？
最直觀的想法是看第i天可以有什么操作。只有買，賣，停三種選擇。而從這三個選擇中取舍，條件是不能同時持有多股。也就是要不就賣出，持有0股；要不就買進，持有1股。
所以T[i][k]可以分成兩種情況：T[i][k][0]和T[i][k][1]持股或不持股。所以有如下遞推情況：
- 初始條件：
T[-1][k][0] = 0, T[-1][k][1] = -Infinity
T[i][0][0] = 0, T[i][0][1] = -Infinity- 遞歸公式：
T[i][k][0] = max(T[i-1][k][0], T[i-1][k][1] + prices[i])
T[i][k][1] = max(T[i-1][k][1], T[i-1][k-1][0] - prices[i])
解釋：
- 當(dāng)-1天0持股時，利潤是0。當(dāng)-1天1持股時，不可能，定義為負無窮。
- 當(dāng)i天0交易0持股時，利潤是0。當(dāng)i天0交易1持股時，不可能，定義為負無窮。
- 當(dāng)i天要變成0持股（清倉）時，可以休停保持i-1天持股，也可以賣出獲得今日股價price。取較大值。
- 當(dāng)i天要變成1持股（買進）時，可以休停保持i-1天持股，也可以買進減去今日股價price。取較大值。
所以最后的最大利潤，就是循環(huán)所有股價之后，最后的清倉利潤T[n-1][k][0]
2. 應(yīng)用范例
以上的六個問題都可以歸作k值不同。cooldown冷卻期和transaction fee交易費的問題也是加上附加條件。
例1：k=1 (easy)
只能交易一次，求最大利潤。
遞推公式變?yōu)椋?/p>
T[i][1][0] = max(T[i-1][1][0], T[i-1][1][1] + prices[i])
T[i][1][1] = max(T[i-1][1][1], T[i-1][0][0] - prices[i]) = max(T[i-1][1][1], -prices[i])
這里利用了初始條件：T[i-1][0][0]等于0。
時間復(fù)雜度O(n)，空間復(fù)雜度O(1)。
public int maxProfit(int[] prices) {
int T_i10 = 0, T_i11 = Integer.MIN_VALUE;
for (int price : prices) {
T_i10 = Math.max(T_i10, T_i11 + price);
T_i11 = Math.max(T_i11, -price);
}
return T_i10;
}
例2：k=+Infinity (easy)
不限交易次數(shù)，求最大利潤。
遞推公式變?yōu)椋?/p>
T[i][k][0] = max(T[i-1][k][0], T[i-1][k][1] + prices[i])
T[i][k][1] = max(T[i-1][k][1], T[i-1][k-1][0] - prices[i]) = max(T[i-1][k][1], T[i-1][k][0] - prices[i])
這里利用了T[i-1][k-1][0] = T[i-1][k][0]
時間復(fù)雜度O(n)，空間復(fù)雜度O(1)。
public int maxProfit(int[] prices) {
int T_ik0 = 0, T_ik1 = Integer.MIN_VALUE;
for (int price : prices) {
int T_ik0_old = T_ik0;
T_ik0 = Math.max(T_ik0, T_ik1 + price);
T_ik1 = Math.max(T_ik1, T_ik0_old - price);
}
return T_ik0;
}
例3：k=2 (hard)
交易次數(shù)為2，求最大利潤。
跟例1同理。
遞推公式變?yōu)椋?/p>
T[i][2][0] = max(T[i-1][2][0], T[i-1][2][1] + prices[i])
T[i][2][1] = max(T[i-1][2][1], T[i-1][1][0] - prices[i])
T[i][1][0] = max(T[i-1][1][0], T[i-1][1][1] + prices[i])
T[i][1][1] = max(T[i-1][1][1], -prices[i])
這里利用了初始條件：T[i-1][0][0]等于0。
時間復(fù)雜度O(n)，空間復(fù)雜度O(1)。
public int maxProfit(int[] prices) {
int T_i10 = 0, T_i11 = Integer.MIN_VALUE,
T_i20 = 0, T_i21 = Integer.MIN_VALUE;
for (int price : prices) {
T_i20 = Math.max(T_i20, T_i21 + price);
T_i21 = Math.max(T_i21, T_i10 - price);
T_i10 = Math.max(T_i10, T_i11 + price);
T_i11 = Math.max(T_i11, -price);
}
return T_i20;
}
例4：k is arbitrary k是任意輸入值 (hard)
交易次數(shù)k為不定值，求最大利潤。
這題是一般情況。重點在于先優(yōu)化一下k的值。
完成任何一次交易都需要一天買入一天賣出，總共2天。
所以一個prices數(shù)組最多交易次數(shù)為n/2次。
如果k>=n/2，可以等同于k=無窮，和例2一樣。
所以先看如果k>=n/2，就用例2方法，如果不，就用一般方法循環(huán)k。如果不優(yōu)化就會出現(xiàn)TLE時間限制錯誤。
時間復(fù)雜度O(kn)，空間復(fù)雜度O(k)。
public int maxProfit(int k, int[] prices) {
if (k >= prices.length >>> 1) {
int T_ik0 = 0, T_ik1 = Integer.MIN_VALUE;
for (int price : prices) {
int T_ik0_old = T_ik0;
T_ik0 = Math.max(T_ik0, T_ik1 + price);
T_ik1 = Math.max(T_ik1, T_ik0_old - price);
}
return T_ik0;
}
int[] T_ik0 = new int[k + 1];
int[] T_ik1 = new int[k + 1];
Arrays.fill(T_ik1, Integer.MIN_VALUE);
for (int price : prices) {
for (int j = k; j > 0; j--) {
T_ik0[j] = Math.max(T_ik0[j], T_ik1[j] + price);
T_ik1[j] = Math.max(T_ik1[j], T_ik0[j - 1] - price);
}
}
return T_ik0[k];
}
例5：k = +Infinity but with cooldown有冷卻期 (medium)
交易次數(shù)k不限，但不能連續(xù)2天交易（賣完隔一天才能買），求最大利潤。
所以遞歸公式由如下：
T[i][k][0] = max(T[i-1][k][0], T[i-1][k][1] + prices[i])
T[i][k][1] = max(T[i-1][k][1], T[i-1][k][0] - prices[i])
變成 i-2：
T[i][k][0] = max(T[i-1][k][0], T[i-1][k][1] + prices[i])
T[i][k][1] = max(T[i-1][k][1], T[i-2][k][0] - prices[i])
時間復(fù)雜度O(n)，空間復(fù)雜度O(1)。
public int maxProfit(int[] prices) {
int T_ik0_pre = 0, T_ik0 = 0, T_ik1 = Integer.MIN_VALUE;
for (int price : prices) {
int T_ik0_old = T_ik0;
T_ik0 = Math.max(T_ik0, T_ik1 + price);
T_ik1 = Math.max(T_ik1, T_ik0_pre - price);
T_ik0_pre = T_ik0_old;
}
return T_ik0;
}
例6：k = +Infinity but with transaction fee有交易費 (medium)
交易次數(shù)k不限，但每次交易有交易費fee，求最大利潤。
所以遞歸公式由如下：
T[i][k][0] = max(T[i-1][k][0], T[i-1][k][1] + prices[i])
T[i][k][1] = max(T[i-1][k][1], T[i-1][k][0] - prices[i])
變成 i-2：
T[i][k][0] = max(T[i-1][k][0], T[i-1][k][1] + prices[i])
T[i][k][1] = max(T[i-1][k][1], T[i-1][k][0] - prices[i] - fee)
or
T[i][k][0] = max(T[i-1][k][0], T[i-1][k][1] + prices[i] - fee)
T[i][k][1] = max(T[i-1][k][1], T[i-1][k][0] - prices[i])
注意有可能integer溢出
時間復(fù)雜度O(n)，空間復(fù)雜度O(1)。
解法1：買入時收費
public int maxProfit(int[] prices, int fee) {
int T_ik0 = 0, T_ik1 = Integer.MIN_VALUE;
for (int price : prices) {
int T_ik0_old = T_ik0;
T_ik0 = Math.max(T_ik0, T_ik1 + price);
T_ik1 = Math.max(T_ik1, T_ik0_old - price - fee);
}
return T_ik0;
}
解法2：賣出時收費（long替換int防止溢出錯誤）
public int maxProfit(int[] prices, int fee) {
long T_ik0 = 0, T_ik1 = Integer.MIN_VALUE;
for (int price : prices) {
long T_ik0_old = T_ik0;
T_ik0 = Math.max(T_ik0, T_ik1 + price - fee);
T_ik1 = Math.max(T_ik1, T_ik0_old - price);
}
return (int)T_ik0;
}
總結(jié)
例4是一般情況的解法，時間復(fù)雜度O(kn)，空間復(fù)雜度O(k)?？梢娊灰鬃畲罄麧櫲Q于：
第i天的操作，最大交易次數(shù)限制k和最后我們手中股票數(shù)額。
例5、例6有一些附加條件不過也是之前的變形。
希望有所幫助，happy coding！
