目录
题目描述
这道题把第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的答案。