01
前言
主要用的技巧是“狀態(tài)機(jī)”，那么什么是“狀態(tài)機(jī)”呢？沒聽過的小伙伴會覺得它很高大尚，但今天我們討論過后，你會發(fā)現(xiàn)其實它就是那么回事。
接下來，我們就以下邊的題目為基礎(chǔ)，講解一下“狀態(tài)機(jī)”是什么。
請看題：
看完題目后是不是覺得無從下手呢，沒關(guān)系，接下來我們進(jìn)入正題。
02
窮舉框架
首先我們會想到，要解決這個問題需要怎么進(jìn)行窮舉，獲取出最大的利潤呢？要窮舉的對象又是什么呢？
既然我們選擇了狀態(tài)機(jī)，那么要窮舉的對象就是是狀態(tài)，窮舉狀態(tài)的一種框架就是下邊的模式:
for 狀態(tài)1 in 狀態(tài)1的所有取值
for 狀態(tài)2 in 狀態(tài)2的所有取值
for ...
dp[狀態(tài)1][狀態(tài)2][...] = 擇優(yōu)（選擇1，選擇2，...）
具體到我們的題目，分析可以知道我們每天都有三種選擇：買入、賣出、臥倒不動，我們用buy、sell、rest表示這三種選擇。
在此基礎(chǔ)上，我們再次分析，可以知道每天是不能隨意選擇這三種選擇的，它的選擇是有限制條件的。
sell必須要在buy之后，buy又必須在sell之后（除了第一次）。而對于rest又有兩種情況，如果是在buy之后rest，那么目前就是持倉狀態(tài)，如果是在sell之后rest，那么目前就是空倉狀態(tài)。而且我們還有一個買入次數(shù)K的限制，所以我們的buy是有限制的，buy<k, k>0。
分析題目，這個問題有三種狀態(tài),第一個是天數(shù)，第二是允許交易的最大次數(shù)k,第三個是當(dāng)前的持有狀態(tài)（空倉還是持倉，我們假設(shè)空倉為0，持倉為1）
看起來還可以理解吧，那么如何窮舉呢？
我們用一個三維數(shù)組dp就可以存儲這幾種狀態(tài)的全部組合，然后就可以用for循環(huán)完成窮舉，如下：
dp[i][k][0 or 1]
0<=i<=n-1,1<=k<=K
//n為天數(shù)，K為最多交易次數(shù)，全部窮舉如下
for 0<=i<n;
for 1<=k<=K;
for s in {0,1};
dp[i][k][s] = max(buy,sell,rest)
如果上邊的表達(dá)式還是沒有看明白，那么我們可以用大白話描述出每一個狀態(tài)的含義，比如說dp[3][2][1] 的含義就是：今天是第三天，我現(xiàn)在手上持有著股票，至今進(jìn)行 2 次交易。再比如 dp[2][3][0] 的含義：今天是第二天，我現(xiàn)在手上沒有持有股票，至今進(jìn)行 3 次交易。這樣就更容易理解了吧。
我們想要的最大利潤值一定是 dp[n - 1][k][0]，也就是最后一天，交易了k次，空倉狀態(tài)。為什么說是空倉狀態(tài)利潤最大呢，可以這么理解，假設(shè)我們手上一共就這么多錢用于買賣股票，不考慮利潤的情況下，如果買入股票變?yōu)槌謧}狀態(tài)，可以看成是我們的總資金減去了買入的資金，實際上我們的資金是變少的，而賣出變?yōu)榭諅}狀態(tài)，可以看成是我們把買入的資金又以不同的價格賣了出去，此時我們的總資金才真的增加了錢數(shù)，對于我們的總資金來說才算真正的盈利了。這其實就是我們平時理財?shù)囊粋€道理，如果買入了股票或基金，只要不賣出，你就不會真正的盈利，同樣也不會真正的虧損，好了這是題外話，之后會有理財專輯專門談?wù)劺碡?，我們回歸正題。
03
狀態(tài)轉(zhuǎn)移框架
我們知道了有多少狀態(tài)，有多少選擇，那么現(xiàn)在我們就開始考慮每種狀態(tài)有哪種選擇，他們之間如何組合。
三種選擇buy、sell、rest是只與持有狀態(tài)相關(guān)的，所以可以畫出一個狀態(tài)轉(zhuǎn)移圖如下：
通過這個圖我們可以清楚的看到0和1之間是如何因為選擇而轉(zhuǎn)換的?？梢詫懗鰻顟B(tài)轉(zhuǎn)移方程如下：
dp[i][k][0]=max(dp[i-1][k][0],dp[i-1][k][1]+prices[i])
max( 選擇rest, 選擇sell )
解釋：今天沒有持有股票有兩種情況
昨天沒有持有，今天沒有操作，所以今天沒有持有
昨天持有股票，今天賣出操作，所以今天沒有持有
dp[i][k][1]=max(dp[i-1][k][1],dp[i-1][k-1][0]-prices[i])
max( 選擇rest, 選擇buyl )
解釋：今天持有股票有兩種情況
昨天持有股票，今天沒有操作，所以今天持有股票
昨天沒有持有，今天買入操作，所以今天持有股票
轉(zhuǎn)移方程中的解釋應(yīng)該很清楚了，如果buy就從總錢數(shù)里減去prices[i]，如果sell就給總錢數(shù)加上prices[i]。那么今天的最大利潤就是在這兩種選擇中選取總錢數(shù)最大的那種情況。而且要保證交易次數(shù)的限制，buy了一次k就增加1，保證k<K。
現(xiàn)在我們已經(jīng)把解題的核心部分，狀態(tài)轉(zhuǎn)移方程寫完了，那么對于題目其實就是套用框架了，不過在套用之前，我們先把一些特殊情況考慮進(jìn)去。
dp[-1][k][0] = 0;
// 因為i>0，所以i=-1代表還沒開始，利潤為0
dp[-1][k][1] = 不存在;
// 還沒開始是不可能持有股票的
dp[i][0][0] = 0;
// k=0代表還沒交易過，利潤當(dāng)然是0
dp[i][0][1] = 不存在;
// k=0代表還沒交易過，不可能持有股票
04
解決題目
第一題：k=1，即最多完成一次交易
直接套用框架如下：
dp[i][1][0] = max(dp[i-1][1][0],dp[i-1][1][1]+prices[i]);
dp[i][1][1] = max(dp[i-1][1][1],dp[i-1][0][0]-prices[i])
= max(dp[i-1][1][1],-prices[i]);
// 因為dp[i-1][0][0]=0
// 可以發(fā)現(xiàn)k都是1，也就是說k不影響狀態(tài)轉(zhuǎn)移，所以可以簡化如下：
dp[i][0] = max(dp[i-1][0],dp[i-1][1]+prices[i]);
dp[i][1] = max(dp[i-1][1],-prices[i]);
同時我們還要考慮當(dāng)i=0的時候，情況特殊，所以我們可以單獨(dú)設(shè)置變量存儲特殊情況
翻譯成最終代碼如下：
public int maxProfit(int[] prices) {
int n=prices.length;
int dp_i_0=0,dp_i_1=Integer.MIN_VALUE;
for(int i=0;i<n;i++){
dp_i_0=Math.max(dp_i_0,dp_i_1+prices[i]);
dp_i_1=Math.max(dp_i_1,-prices[i]);
}
return dp_i_0;
}
相信小伙伴們前邊的內(nèi)容理解清楚后，最終的代碼是能夠看懂的，我們繼續(xù)看下一題。
第二題，k=+infinity，及不限制交易次數(shù)
如果k=+infinity，那么就可以認(rèn)為k-1=k，所以可以引入改寫框架如下：
dp[i][k][0] = max(dp[i-1][k][0],dp[i-1][k][1]+prices[i]);
dp[i][k][1] = max(dp[i-1][k][1],dp[i-1][k-1][0]-prices[i])
= max(dp[i-1][k][1],dp[i-1][k][0]-prices[i]);
// 可以發(fā)現(xiàn)k值全部相同，也就是說k不影響狀態(tài)轉(zhuǎn)移，所以可以簡化如下：
dp[i][0] = max(dp[i-1][0],dp[i-1][1]+prices[i]);
dp[i][1] = max(dp[i-1][1],dp[i-1][0]-prices[i]);
直接翻譯成代碼如下：
public int maxProfit(int[] prices) {
int n=prices.length;
int dp_i_0=0,dp_i_1=Integer.MIN_VALUE;
for(int i=0;i<n;i++){
int temp=dp_i_0;
dp_i_0=Math.max(dp_i_0,dp_i_1+prices[i]);
dp_i_1=Math.max(dp_i_1,temp-prices[i]);
}
return dp_i_0;
}
第三題，k=+infinity ,而且?guī)в欣鋬銎?/span>
解釋一下題目，就是，賣出股票后，你無法在第二天買入股票 (即冷凍期為 1 天)。不限制交易次數(shù)
狀態(tài)轉(zhuǎn)移方程如下：
dp[i][0] = max(dp[i-1][0],dp[i-1][1]+prices[i]);
dp[i][1] = max(dp[i-1][1],dp[i-2][0]-prices[i]);
// 第i天選擇buy的時候，要從i-2的狀態(tài)轉(zhuǎn)移（冷凍期1天）
直接翻譯成代碼如下：
public int maxProfit(int[] prices) {
int n=prices.length;
int dp_i_0=0,dp_i_1=Integer.MIN_VALUE;
int dp_pre_0=0;//代表dp[i-2][0]
for(int i=0;i<n;i++){
int temp=dp_i_0;
dp_i_0=Math.max(dp_i_0,dp_i_1+prices[i]);
dp_i_1=Math.max(dp_i_1,dp_pre_0-prices[i]);
dp_pre_0=temp;
}
return dp_i_0;
}
第四題，k=+infinity,帶手續(xù)費(fèi)
手續(xù)費(fèi)題目中這樣描述：這里的一筆交易指買入持有并賣出股票的整個過程，每筆交易你只需要為支付一次手續(xù)費(fèi)。
那么狀態(tài)轉(zhuǎn)移方程中，我們每次賣出的時候，把手續(xù)費(fèi)減掉就可以了，如下：
dp[i][0] = max(dp[i-1][0],dp[i-1][1]+prices[i]);
dp[i][1] = max(dp[i-1][1],dp[i-1][0]-prices[i]-fee);
// fee代表手續(xù)費(fèi)，兩個式子里隨便一個減掉一次就可以了，可以看成是買入的時候交手續(xù)費(fèi)或者賣出的時候交手續(xù)費(fèi)
直接翻譯成代碼如下：
public int maxProfit(int[] prices,int fee) {
int n=prices.length;
int dp_i_0=0,dp_i_1=Integer.MIN_VALUE;
for(int i=0;i<n;i++){
int temp=dp_i_0;
dp_i_0=Math.max(dp_i_0,dp_i_1+prices[i]);
dp_i_1=Math.max(dp_i_1,temp-prices[i]-fee);
}
return dp_i_0;
}
05
總結(jié)
好了，看到這里以上4道關(guān)于股票買賣的算法題我們就完美解決了，小伙伴們看懂了嗎，希望大家仔細(xì)思考解題思路，能實際運(yùn)用這套框架哦，這是關(guān)于股票買賣算法的第一篇文章，后續(xù)會有補(bǔ)充內(nèi)容，對剩下比較復(fù)雜的題目提供解題方法，歡迎閱讀我的下一篇文章，一起研究算法吧。
聯(lián)系客服
