目錄

題目描述

第一步，明確并理解dp數組及下標的含義

第二步，分析明確并理解遞推公式

1.求dp[i][j].holding

2.求dp[i][j].sold

第三步，理解dp數組如何初始化

第四步，理解遍歷順序

代碼

---

題目描述

這道題把第123題推廣為一般情形。第123題限制最多可以完成兩筆交易，這道題改為最多可以完成k筆交易。因此，兩道題沒有本質區別。仍然用第123題的思路來分析。

第一步，明確并理解dp數組及下標的含義

//最多可以完成k筆交易,用j表示交易的序號，j從0開始起算表示第一次交易，j取值范圍是[0,k-1]

//約定好，下文提到的【第j只股票】指的是第j次買入的股票

//dp[i][j].holding表示到第i天結束時，處于持有第j只股票的狀態的最大利潤

//dp[i][j].sold表示到第i天結束時，處于已經賣出第j只股票但是還沒有買入第j+1只股票的狀態下的最大利潤

    struct State{int holding = 0;int sold = 0;};int n = prices.size();//最多可以完成k筆交易,用j表示交易的序號，j從0開始起算表示第一次交易，j取值范圍是[0,k-1]//約定好，下文提到的【第j只股票】指的是第j次買入的股票//dp[i][j].holding表示到第i天結束時，處于持有第j只股票的狀態的最大利潤//dp[i][j].sold表示到第i天結束時，處于已經賣出第j只股票但是還沒有買入第j+1只股票的狀態下的最大利潤vector<vector<State>> dp(n);for(int i =0;i <n;i++)dp[i].resize(k);

第二步，分析明確并理解遞推公式

1.求dp[i][j].holding

//到第i天結束時處于持有第j只股票的狀態，有兩種可能的原因：

//一是前一天(第i-1天)結束時就已經處于持有第j只股票的狀態(對應dp[i-1][j].holding)，第i天什么也不做。

//二是第i天買入了第j只股票(需支付prices[i])，第i天能買入第j只股票的前提是前一天(第i-1天)結束時處于已經賣出第j-1只股票但是還沒有買入第j只股票的狀態(對應dp[i-1][j-1].sold)。j如果是0就沒有第j-1只股票,需要特別處理。

int temp = (j > 0) ? (dp[i-1][j-1].sold) : (0);

dp[i][j].holding = max(dp[i-1][j].holding,temp - prices[i]);

2.求dp[i][j].sold

//到第i天結束時處于已經賣出第j只股票但是還沒有買入第j+1只股票的狀態，有兩種可能的原因：

//一是前一天(第i-1天)結束時就已經處于已經賣出第j只股票但是還沒有買入第j+1只股票的狀態(對應dp[i-1][j].sold),第i天什么也不做

//二是第i天賣出了第j只股票(收入prices[i]),第i天能賣出第j只股票的前提是前一天(第i-1天)結束時處于持有第j只股票的狀態(對應狀態dp[i-1][j].holding)

dp[i][j].sold = max(dp[i-1][j].sold,dp[i-1][j].holding + prices[i]);

        for(int i = 1;i < n;i++){for(int j = 0;j < k;j++){//到第i天結束時處于持有第j只股票的狀態，有兩種可能的原因：//一是前一天(第i-1天)結束時就已經處于持有第j只股票的狀態(對應dp[i-1][j].holding)，第i天什么也不做。//二是第i天買入了第j只股票(需支付prices[i])，第i天能買入第j只股票的前提是前一天(第i-1天)結束時處于已經賣出第j-1只股票但是還沒有買入第j只股票的狀態(對應dp[i-1][j-1].sold)。j如果是0就沒有第j-1只股票,需要特別處理。int temp = (j > 0) ? (dp[i-1][j-1].sold) : (0);dp[i][j].holding = max(dp[i-1][j].holding,temp - prices[i]);//到第i天結束時處于已經賣出第j只股票但是還沒有買入第j+1只股票的狀態，有兩種可能的原因：//一是前一天(第i-1天)結束時就已經處于已經賣出第j只股票但是還沒有買入第j+1只股票的狀態(對應dp[i-1][j].sold),第i天什么也不做//二是第i天賣出了第j只股票(收入prices[i]),第i天能賣出第j只股票的前提是前一天(第i-1天)結束時處于持有第j只股票的狀態(對應狀態dp[i-1][j].holding)dp[i][j].sold = max(dp[i-1][j].sold,dp[i-1][j].holding + prices[i]);}}

第三步，理解dp數組如何初始化

for(int j = 0;j <k;j++){

dp[0][j].holding = -prices[0];//到第0天結束時處于持有第j只股票的狀態，可以理解為對第0天的股票買了又賣重復j-1次之后再買入

dp[0][j].sold = 0;//到第0天結束時處于已經賣出第j只股票但是還沒有買入第j+1只股票的狀態，可以理解為對第0天的股票買了又賣重復j次

}

        for(int j = 0;j <k;j++){dp[0][j].holding = -prices[0];//到第0天結束時處于持有第j只股票的狀態，可以理解為對第0天的股票買了又賣重復j-1次之后再買入dp[0][j].sold = 0;//到第0天結束時處于已經賣出第j只股票但是還沒有買入第j+1只股票的狀態，可以理解為對第0天的股票買了又賣重復j次}

第四步，理解遍歷順序

由遞推公式

int temp = (j > 0) ? (dp[i-1][j-1].sold) : (0);

dp[i][j].holding = max(dp[i-1][j].holding,temp - prices[i]);

dp[i][j].sold = max(dp[i-1][j].sold,dp[i-1][j].holding + prices[i]);

可知日期的序號i（或者說股價的序號）應該從小到大遍歷。

可知買入的股票的序號j，也應該從小到大遍歷。

代碼

class Solution {struct State{int holding = 0;int sold = 0;};
public:int maxProfit(int k, vector<int>& prices) {int n = prices.size();//最多可以完成k筆交易,用j表示交易的序號，j從0開始起算表示第一次交易，j取值范圍是[0,k-1]//約定好，下文提到的【第j只股票】指的是第j次買入的股票//dp[i][j].holding表示到第i天結束時，處于持有第j只股票的狀態的最大利潤//dp[i][j].sold表示到第i天結束時，處于已經賣出第j只股票但是還沒有買入第j+1只股票的狀態下的最大利潤vector<vector<State>> dp(n);for(int i =0;i <n;i++)dp[i].resize(k);for(int j = 0;j <k;j++){dp[0][j].holding = -prices[0];//到第0天結束時處于持有第j只股票的狀態，可以理解為對第0天的股票買了又賣重復j-1次之后再買入dp[0][j].sold = 0;//到第0天結束時處于已經賣出第j只股票但是還沒有買入第j+1只股票的狀態，可以理解為對第0天的股票買了又賣重復j次}for(int i = 1;i < n;i++){for(int j = 0;j < k;j++){//到第i天結束時處于持有第j只股票的狀態，有兩種可能的原因：//一是前一天(第i-1天)結束時就已經處于持有第j只股票的狀態(對應dp[i-1][j].holding)，第i天什么也不做。//二是第i天買入了第j只股票(需支付prices[i])，第i天能買入第j只股票的前提是前一天(第i-1天)結束時處于已經賣出第j-1只股票但是還沒有買入第j只股票的狀態(對應dp[i-1][j-1].sold)。j如果是0就沒有第j-1只股票,需要特別處理。int temp = (j > 0) ? (dp[i-1][j-1].sold) : (0);dp[i][j].holding = max(dp[i-1][j].holding,temp - prices[i]);//到第i天結束時處于已經賣出第j只股票但是還沒有買入第j+1只股票的狀態，有兩種可能的原因：//一是前一天(第i-1天)結束時就已經處于已經賣出第j只股票但是還沒有買入第j+1只股票的狀態(對應dp[i-1][j].sold),第i天什么也不做//二是第i天賣出了第j只股票(收入prices[i]),第i天能賣出第j只股票的前提是前一天(第i-1天)結束時處于持有第j只股票的狀態(對應狀態dp[i-1][j].holding)dp[i][j].sold = max(dp[i-1][j].sold,dp[i-1][j].holding + prices[i]);}}int max_profit = 0;for(int j = 0;j < k;j++){if(dp[n-1][j].sold > max_profit)max_profit = dp[n-1][j].sold;}return max_profit;}
};

把本題的代碼中的k改成2，直接可以用作123. Best Time to Buy and Sell Stock III的答案。