给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: p=[2,4,1], k = 2
输出: 2
解释: 在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
示例 2:
输入: p=[3,2,6,5,0,3], k = 2
输出: 7
解释: 在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。
分析
当题目中 k k k大于表格数量的 1 2 \frac{1}{2} 21的时候，就相当于无限制了，这个时候采用贪心算法更好。否则就得用动态规划。
动态规划
根据上篇介绍动态规划设计的方法， d p ( p , k ) dp(p,k) dp(p,k)应该代表着当数组为p时候最多完成k笔交易，所能获得的最大利润。然后找这个问题中股民遇到的选择情景，股民每一天都可以选择买与不买，卖与不卖，通过这些选择来使自己利益最大化，需要注意的是买与不买是在自己不持股票的状态下，卖与不卖是在自己持股的状态下。所以每一天的两种状态都在dp范围内。
假设股民在i-1天之前在两种情况下都已经是做出了自己最优的选择了，那么在第i天我们应该如何做出抉择呢？
我们假设 d p ( i , j ) dp(i,j) dp(i,j)代表包括第i天的前i天的股票给最大j笔交易机会，且当前不持股情况下，最大利润能是多少。很明显这和原问题是同样的结构。 这里包含了第i天的选择操作。
我们再假设 h o l d ( i , j ) hold(i,j) hold(i,j)代表包括第i天的前i天的股票给最大j笔交易机会，且当前持股情况下，你目前的最大金钱数能是多少。这里和上面的区别在于，在这之前你是花了前买了一个股票的，至于是第i天买的还是更早买的，无所谓了。
我们要让股民利益最大化，在第i天要做出选择：
- 在当天不持股的情况下，说明要么他本来就不持股，要么说明他今天卖掉了自己的股票,消耗了一次交易机会，我们选择一个能让他利益最大的情况
d p ( i , j ) = m a x ( d p ( i − 1 , j ) , h o l d ( i − 1 , j − 1 ) + p [ i ] ) dp(i,j)=max(dp(i-1,j),hold(i-1,j-1)+p[i]) dp(i,j)=max(dp(i−1,j),hold(i−1,j−1)+p[i]) - 在当天持股的情况下，说明要么他本来就持股，要么说明他今天买了股票，我们选择一个能让他利益最大的情况
h o l d ( i , j ) = m a x ( h o l d ( i − 1 , j ) , d p ( i − 1 , j ) − p [ i ] ) hold(i,j)=max(hold(i-1,j),dp(i-1,j)-p[i]) hold(i,j)=max(hold(i−1,j),dp(i−1,j)−p[i])
写出表达式后我们要计算初始值：
d p ( 0 , j ) = 0 , j = 0 , 1 , 2... k h o l d ( 0 , j ) = − p [ 0 ] , j = 0 , 1 , 2... k d p ( i , 0 ) = 0 , i = 0 , 1 , 2... p . s i z e − 1 dp(0,j)=0,j=0,1,2...k\\ hold(0,j)=-p[0],j=0,1,2...k\\ dp(i,0)=0,i=0,1,2...p.size-1\\ dp(0,j)=0,j=0,1,2...khold(0,j)=−p[0],j=0,1,2...kdp(i,0)=0,i=0,1,2...p.size−1
贪心算法
贪心比dp要容易，当 k k k大于表格数量的 1 2 \frac{1}{2} 21的时候，我们认为是无限制买卖。所以只要是涨价，我们都买。把原数列差分，然后把大于0的都加起来就是。
c++代码
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
vector<vector<int>> dp,hold;
if(prices.size()==0)return 0;
if(k>prices.size()/2){
return greedy(prices);
}
dp=vector<vector<int>>(prices.size(),vector<int>(k+1,0));
hold=vector<vector<int>>(prices.size(),vector<int>(k+1,0));
for(int i=0;i<=k;i++){
hold[0][i]=-prices[0];
}
for(int i=1;i<prices.size();i++){
hold[i][0]=max(hold[i-1][0],-prices[i]);
}
for(int i=1;i<prices.size();i++){
for(int j=1;j<=k;j++){
dp[i][j]=max(dp[i-1][j],hold[i-1][j-1]+prices[i]);
hold[i][j]=max(hold[i-1][j],dp[i-1][j]-prices[i]);
}
}
return dp[prices.size()-1][k];
}
int greedy(vector<int>& prices){
int ans=0;
for(int i=0;i<prices.size()-1;i++){
ans+=max(0,prices[i+1]-prices[i]);
}
return ans;
}
};