动态规划
123. 买卖股票的最佳时机 III
题意：给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
实例：
思路：由题意可知，我们最多进行两次股票的买卖，两次买卖是存在一定状态关系的。我们第一次买卖所得的钱会影响到第二次买卖的结果，即最终结果。因此我们在创建数组时，需要创建四个状态：0表示第一次买入股票的全部金额，1表示第一次卖出股票的全部金额，2表示第二次买入股票的全部金额，3表示第二次卖出股票的全部金额。第一次买入和卖出的递归公式我们在之前的题目中也给出过，而第二次买入则需要第一次卖出的金额决定，第二次卖出则需要第二次买入觉得，以此类推，代码如下。
C++代码：
int maxProfit(vector<int>& prices) {
vector<vector<int>> dp(prices.size(),vector<int>(4));
//四种状态：0表示不操作，1表示第一次买入，2表示第一次卖出，3表示第二次买入，4表示第二次卖出
dp[0][0]=-prices[0],dp[0][1]=0,dp[0][2]=-prices[0],dp[0][3]=0;
for(int i=1;i<prices.size();i++)
{
dp[i][0]=max(dp[i-1][0],-prices[i]);
dp[i][1]=max(dp[i-1][1],dp[i-1][0]+prices[i]);
dp[i][2]=max(dp[i-1][2],dp[i-1][1]-prices[i]);
dp[i][3]=max(dp[i-1][3],dp[i-1][2]+prices[i]);
}
return dp[prices.size()-1][3];
}188. 买卖股票的最佳时机 IV
题意：给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
实例：
思路：本题就是对买卖股票这类问题的一个总结。我们从前面的题不难看出，对于只能一次的交易，我们的0表示买入股票后剩余的钱，1表示卖出股票剩余的钱，以此类推，对于k次买卖股票，偶数(包括0)表示买入股票的钱，奇数表示卖出股票的钱，这样我们的数组创建，就有k*2种状态；在递推公式中，我们只需要在使用一次for循环，将状态转移方程以循环的方式实现即可
C++代码：
int maxProfit4(int k, vector<int>& prices) {
vector<vector<int>> dp(prices.size(), vector<int>(k * 2 + 1));
//0表示买入，1表示卖出，即偶数表示买入，奇数表示卖出
for (int i = 1; i < k * 2 + 1; i += 2)
{
dp[0][i] = -prices[0];
}
for (int i = 1; i < prices.size(); i++)
{
for (int j = 0; j <= k * 2 + 1 - 2; j += 2)
{
dp[i][j + 1] = max(dp[i - 1][j+1], dp[i - 1][j] - prices[i]);
dp[i][j + 2] = max(dp[i - 1][j+2], dp[i - 1][j+1] + prices[i]);
}
}
return dp[prices.size() - 1][k * 2];
}