力扣對應題目鏈接：188. 買賣股票的最佳時機 IV - 力扣（LeetCode）

牛客對應題目鏈接：買賣股票的最好時機(四)_牛客題霸_牛客網 (nowcoder.com)

---

一、分析題目

1、狀態表示

為了更加清晰的區分買入和賣出，我們換成有股票和無股票兩個狀態。

• f[i][j] 表示：第 i 天結束后，完成了 j 筆交易，此時處于有股票狀態的最大收益。
• g[i][j] 表示：第 i 天結束后，完成了 j 筆交易，此時處于無股票狀態的最大收益。

---

2、狀態轉移方程

對于 f[i][j]，也有兩種情況能在第 i 天結束之后，完成 j 筆交易，此時手里有股票的狀態：

• 在 i-1 天的時候，手里有股票，并且交易了 j 次。在第 i 天的時候，啥也不干。此時的收益為 f[i - 1][j]。
• 在 i-1 天的時候，手里沒有股票，并且交易了 j 次。在第 i 天的時候，買了股票。那么 i 天結束之后，就有股票了。此時的收益為 g[i - 1][j] - prices[i]。

上述兩種情況，我們需要的是最大值，因此 f 的狀態轉移方程為：

f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]

對于 g[i][j]，我們有下?兩種情況能在第 i 天結束之后，完成 j 筆交易，此時手里沒有股票的狀態：

• 在 i-1 天的時候，手里沒有股票，并且交易了 j 次。在第 i 天的時候，啥也不干。此時的收益為 g[i - 1][j]。
• 在 i-1 天的時候，手里有股票，并且交易了 j - 1 次。在第 i 天的時候，把股票賣了。那么 i 天結束之后，我們就交易了 j 次。此時的收益為 f[i - 1][j - 1] + prices[i]。

上述兩種情況，我們需要的是最大值，因此 g 的狀態轉移方程為：

g[i][j] = max(g[i - 1][j], f[i - 1][j - 1] + prices[i])

它們之間交易關系如下：

---

3、初始化

• 當處于第 0 天的時候，只能處于買入過?次的狀態，此時的收益為 -prices[0] ，因此 f[0][0] = - prices[0] 。
• 為了取 max 的時候，?些不存在的狀態起不到干擾的作?，我們統統將它們初始化為 -INF（用?INT_MIN 在計算過程中會有溢出的風險，這? INF 折半取 0x3f3f3f3f ，足夠小即可）。

---

4、填表順序

從上往下填每一行，每一行從左往右，兩個表?起填。

---

5、返回值

返回處于賣出狀態的最大值，但是我們也不知道是交易了幾次，因此返回 g 表最后一行的最大值。

---

6、優化

我們的交易次數是不會超過整個天數的一半的，因此我們可以先把 k 處理一下，優化一下問題的規模：k = min(k, n / 2)。

---

二、代碼

//力扣
//【動態規劃-二維dp-2個狀態】
class Solution {//f[i][j]:第i天結束后，完成了j次交易，此時處于“買入”狀態下的最大利潤//g[i][j]:第i天結束后，完成了j次交易，此時處于“賣出”狀態下的最大利潤
private:const int INF=0x3f3f3f3f;
public:int maxProfit(int k, vector<int>& prices) {int n=prices.size();k=min(k, n/2); //優化:處理最多交易次數vector<vector<int>> f(n, vector<int>(k+1, -INF));vector<vector<int>> g(n, vector<int>(k+1, -INF));f[0][0]=-prices[0], g[0][0]=0;for(int i=1; i<n; i++){for(int j=0; j<=k; j++){f[i][j]=max(f[i-1][j], g[i-1][j]-prices[i]);g[i][j]=g[i-1][j];if(j>=1) g[i][j]=max(g[i][j], f[i-1][j-1]+prices[i]);}}int res=0;for(int j=0; j<=k; j++)res=max(res, g[n-1][j]);return res;}
};//【動態規劃-二維dp-2k+1個狀態】
class Solution {//dp[i][0] -- 沒有操作//下面j為奇數：買入；j為偶數：賣出 (j的范圍：1~2k-1)//dp[i][j] -- 第1~k次買入//dp[i][j+1] -- 第1~k次賣出
public:int maxProfit(int k, vector<int>& prices) {int n=prices.size();vector<vector<int>> dp(n, vector<int>(2*k+1));for(int j=1; j<2*k; j+=2)dp[0][j]=-prices[0];for(int i=1; i<n; i++){for(int j=0; j<2*k; j+=2){dp[i][j+1]=max(dp[i-1][j+1], dp[i-1][j]-prices[i]);dp[i][j+2]=max(dp[i-1][j+2], dp[i-1][j+1]+prices[i]);}}return dp[n-1][2*k];}
};

//牛客
#include <iostream>
#include <cstring>
using namespace std;const int INF=0x3f3f3f3f;
const int N=1010, M=110;
int prices[N];
int f[N][M], g[N][M];
//f[i][j]:第i天結束后，完成了j次交易，此時處于“買入”狀態下的最大利潤
//g[i][j]:第i天結束后，完成了j次交易，此時處于“賣出”狀態下的最大利潤int main()
{int n, k;cin >> n >> k;for(int i=0; i<n; i++)cin >> prices[i];memset(f, -INF, sizeof(f));memset(g, -INF, sizeof(g));int res=0;f[0][0]=-prices[0], g[0][0]=0;for(int i=1; i<n; i++){for(int j=0; j<=k; j++){f[i][j]=max(f[i-1][j], g[i-1][j]-prices[i]);g[i][j]=g[i-1][j];if(j>0) g[i][j]=max(g[i][j], f[i-1][j-1]+prices[i]);res=max(res, g[i][j]);}}cout << res << endl;return 0;
}//值得學習的代碼
#include <iostream>
using namespace std;const int N = 1010, M = 110;int n, k, p[N];
int f[N][M], g[N][M];int main()
{cin >> n >> k;for(int i = 0; i < n; i++) cin >> p[i];k = min(k, n / 2);for(int j = 0; j <= k; j++) f[0][j] = g[0][j] = -0x3f3f3f3f;f[0][0] = -p[0], g[0][0] = 0;for(int i = 1; i < n; i++){for(int j = 0; j <= k; j++){f[i][j] = max(f[i - 1][j], g[i - 1][j] - p[i]);g[i][j] = g[i - 1][j];if(j >= 1) g[i][j] = max(g[i][j], f[i - 1][j - 1] + p[i]);}}int ret = 0;for(int j = 0; j <= k; j++) ret = max(ret, g[n - 1][j]);cout << ret << endl;return 0;
}

---

三、反思與改進

買賣股票這種類似有系列的題目，需要把核心知識點徹底弄熟。