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).
买股票问题升级版，可以购买k次。利用买股票问题的第三个变式，可以构造两个dp数组。
sell[i]表示第i次卖出后最大持有的金钱
buy[i]表示第i次买入后最大持有的金钱
卖出的钱由买入的钱加上当前股票卖出的钱，买入的钱由前一次卖出的钱减去当前买股票花去的，因此可以得到两个转移方程
sell[j] = max(sell[j], buy[j] + prices[i]); buy[j] = max(buy[j], sell[j-1] - prices[i]);有个小陷阱，k可能很大，达到比总天数多，这种情况下，问题等价于买卖任意次，直接贪心就可以了 class Solution { public: int maxProfit(int k, vector<int>& prices) { if(k > prices.size()) { int res = 0; for(int i = 1 ; i < prices.size(); i++) if(prices[i] > prices[i-1]) res += prices[i]-prices[i-1]; return res; } vector<int> sell(k+1, 0), buy(k+1, INT_MIN); for(int i = 0; i < prices.size() ; i++) { for(int j = k; j > 0 ; j--) { sell[j] = max(sell[j], buy[j] + prices[i]); buy[j] = max(buy[j], sell[j-1] - prices[i]); } } return sell[k]; } };