狀態(tài)分類(lèi)：
f[i,j,0]考慮前i只股票，進(jìn)行了j筆交易，目前未持有股票 所能獲得最大利潤(rùn)
f[i,j,1]考慮前i只股票，進(jìn)行了j筆交易，目前持有股票 所能獲得最大利潤(rùn)
狀態(tài)轉(zhuǎn)移：
f[i][j][0] = Math.max(f[i-1][j][0],f[i-1][j][1]+prices[i]);
f[i][j][1] = Math.max(f[i-1][j][1],f[i-1][j-1][0]-prices[i]);
?
文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-719156.html
class Solution {
static int INF = 0x3f3f3f3f;
public int maxProfit(int k, int[] prices) {
int n = prices.length;
int f[][][] = new int[n+1][k+1][2];
for(int i = 0;i <= n;i++){
for(int j = 0;j <= k;j++){
Arrays.fill(f[i][j],-INF);
}
}
for(int i = 0;i <= n;i++)f[i][0][0] = 0;
for(int i = 1;i <= n;i++){
for(int j = 1;j <= k;j++){
f[i][j][0] = Math.max(f[i-1][j][0],f[i-1][j][1]+prices[i-1]);
f[i][j][1] = Math.max(f[i-1][j][1],f[i-1][j-1][0]-prices[i-1]);
}
}
int ans = 0;
for(int i = 0;i <= k;i++){
ans = Math.max(ans,f[n][i][0]);
}
return ans;
}
}還有一位大佬的看不懂的極妙解法--滾動(dòng)的dp？文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-719156.html
// java
class Solution {
public int maxProfit(int k, int[] prices) {
int[] buy = new int[k], sell = new int[k];
Arrays.fill(buy, -prices[0]);
for (int i = 1; i < prices.length; i++) {
for (int j = 0, pre = 0; j < k; j++) {
buy[j] = (pre = Math.max(buy[j], pre - prices[i]));
sell[j] = (pre = Math.max(sell[j], pre + prices[i]));
}
}
return Math.max(sell[k - 1], 0);
}
}到了這里，關(guān)于動(dòng)態(tài)規(guī)劃-狀態(tài)機(jī)（188. 買(mǎi)賣(mài)股票的最佳時(shí)機(jī) IV）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![算法[動(dòng)態(tài)規(guī)劃]---買(mǎi)賣(mài)股票最佳時(shí)機(jī)](https://imgs.yssmx.com/Uploads/2024/02/708618-1.png)
