动态规划18：188. 买卖股票的最佳时机 IV

动态规划解题步骤：

1.确定状态表示：dp[i]是什么

2.确定状态转移方程：dp[i]等于什么

3.初始化：确保状态转移方程不越界

4.确定填表顺序：根据状态转移方程即可确定填表顺序

5.确定返回值

题目链接：188. 买卖股票的最佳时机 IV - 力扣（LeetCode）

题解：

本题与动态规划17：123. 买卖股票的最佳时机 III 几乎无异

1.状态表示：

f[k][i]表示截止第i天，第i天为可买入状态的最大利润，且当前已交易k次

g[k][i]表示截止第i天，第i天为可卖出状态的最大利润，且当前已交易k次

2.状态转移方程：

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

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

3.初始化：初始化第一列为负无穷（-0x3f3f3f3f），另外 f[0][0]=0   g[0][0]=-prices[0];

注意：对于f表，其本应该初始化第一行和第一列，但是为了优化代码和g表保持一致，可以只初始化第一列，对于第一行的数据只需对其状态转移方程添加位置判断即可，对于不合法的位置其状态转移方程为f[k][i-1]，合法位置的状态转移方程为max(f[k][i-1],g[k-1][i-1]+prices[i])

4.填表顺序：从上往下，从左往右，两个表一起填

5.返回值：返回第n-1天为可买入状态的最大利润（交易次数可能为0、1、2......K）所以需要遍历第n-1列

class Solution {
public:int maxProfit(int K, vector<int>& prices) {const int INF=0x3f3f3f3f;//f[k][i]表示截止第i天，第i天为可买入状态的最大利润，且当前已交易k次//g[k][i]表示截止第i天，第i天为可卖出状态的最大利润，且当前已交易k次//第i天为可买入状态，则前一天有两种情况：前一天为可买入状态，交易次数相同，今天什么也没做；//                                   前一天为可卖出状态，交易次数少1，今天卖出了股票//f[k][i]=max(f[k][i-1],g[k-1][i-1]+prices[i])//第i天为可卖出状态，则前一天有两种情况：前一天为可卖出状态，交易次数相同，今天什么也没做//                                   前一天为可买入状态，交易次数相同，今天买了股票//g[k][i]=max(g[k][i-1],f[k][i-1]-prices[i])size_t n=prices.size();//处理边界条件if(n==1) return 0;//创建dp表vector<vector<int>> f(K+1,vector<int>(n,-INF));vector<vector<int>> g(K+1,vector<int>(n,-INF));//初始化（创建dp表时已初始化一部分，相当于初始化了第一列）f[0][0]=0;g[0][0]=-prices[0];//填表for(int k=0;k<=K;++k){for(int i=1;i<n;++i){if(k-1>=0) f[k][i]=max(f[k][i-1],g[k-1][i-1]+prices[i]);else f[k][i]=f[k][i-1];g[k][i]=max(g[k][i-1],f[k][i-1]-prices[i]);}}//返回值int ans=INT_MIN;for(int k=0;k<=K;++k)if(f[k][n-1]>ans) ans=f[k][n-1];return ans;}
};