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次买入后最大持有的金钱
卖出的钱由买入的钱加上当前股票卖出的钱，买入的钱由前一次卖出的钱减去当前买股票花去的，因此可以得到两个转移方程
代码语言：javascript复制sell[j] = max(sell[j], buy[j] prices[i]);
buy[j] = max(buy[j], sell[j-1] - prices[i]);有个小陷阱，k可能很大，达到比总天数多，这种情况下，问题等价于买卖任意次，直接贪心就可以了
代码语言：javascript复制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];
}
};
