Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most k transactions.
Note: You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
Example 1:
Input: [2,4,1], k = 2 Output: 2 Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.Example 2:
Input: [3,2,6,5,0,3], k = 2 Output: 7 Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4. Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.题解：跟股票问题III一样，只是前者k=2，这里放到一起，不难定义出状态dp[i][j]表示第i天最多j次交易的最大利益，也就是
dp[i][j]=max(dp[i-1][j],prices[i]-prices[k]+dp[k][j-1])这里是对所有的k小于i，如果遍历求出需要三重循环，但是观察第二项跟k有关的式子prices[k]-dp[k][j-1]只跟j-1有关也就是可以在里面是i循环中前面定义记录一个mink来维护这个式子的最小值，利用滚动 数组还可以优化下空间，即可以去掉i这层维度，这里难点在于mink=prices[k]-dp[k][j-1]的更新，因为 dp[j-1]没有维度k对于当前i 层循环dp[j-1]只表示dp[j-1][n]要使得mink记录dp[j-1]在i之前的信息，可以提前循环i层再循环j并把mink变成j的数组，这样mink[j]=min(mink[j],prices[k]-dp[j-1]),从而实现了对外层i由于外层还没循环到n所以mink[j]记录的是i之前的最小值
代码：
class Solution { public: int maxProfit(int k, vector<int>& prices) { int n = prices.size(); if(k>n) return solveMaxProfit(prices); vector<vector<int>> dp(k+1,vector<int>(n+1,0)); for(int j=1;j<=k;j++){ int mink = INT_MAX; for(int i=1;i<=n;i++){ mink=min(mink,prices[i-1]-dp[j-1][i]); dp[j][i]=max(dp[j][i-1],prices[i-1]-mink); } } return dp[k][n]; } int solveMaxProfit(vector<int> &prices) { int res = 0; for (int i = 1; i < prices.size(); ++i) { if (prices[i] - prices[i - 1] > 0) { res += prices[i] - prices[i - 1]; } } return res; } };最优化：
class Solution { public: int maxProfit(int k, vector<int>& prices) { int n = prices.size(); if(k>n) return solveMaxProfit(prices); vector<int> dp(k+1); vector<int> mink(k+1,INT_MAX); for(int i=1;i<=n;i++){ for(int j=1;j<=k;j++){ mink[j]=min(mink[j],prices[i-1]-dp[j-1]); dp[j]=max(dp[j],prices[i-1]-mink[j]); } } return dp[k]; } int solveMaxProfit(vector<int> &prices) { int res = 0; for (int i = 1; i < prices.size(); ++i) { if (prices[i] - prices[i - 1] > 0) { res += prices[i] - prices[i - 1]; } } return res; } };这里的坑是k大于prices长度的处理！！
