123 买卖股票的最佳时机 III
思路：创建一个二维的dp数组来存储最大利润。dp数组的大小为[n][5]，其中n是股票价格数组的大小，5是表示交易的状态数。在这个问题中，状态是指交易的过程，每个状态由前一状态转移得到。
首先设置dp[0][1]和dp[0][3]为-prices[0]，因为在第一天，只能买入一次。
然后，从第二天开始，使用状态转移方程更新dp数组中的值。根据问题描述，每个状态都是由前一状态转移得到的。
更新dp[i][0]时，由于是不做任何交易，所以前一状态的利润保持不变。
更新dp[i][1]时，从前一状态dp[i-1][1]或者dp[i-1][0] - prices[i]（表示在前一状态不持有股票的情况下买入）得到。
更新dp[i][2]时，从前一状态dp[i-1][2]或者dp[i-1][1] + prices[i]（表示在前一状态持有股票的情况下卖出）得到。
更新dp[i][3]时，从前一状态dp[i-1][3]或者dp[i-1][2] - prices[i]（表示在前一状态不持有股票的情况下买入）得到。
更新dp[i][4]时，从前一状态dp[i-1][4]或者dp[i-1][3] + prices[i]（表示在前一状态持有股票的情况下卖出）得到。
最后，返回dp[n-1][4]（其中n是prices数组的长度），因为在最后一个状态下，持有的股票数量必须为0，而dp[n-1][4]表示在最后一个状态下卖出所有的股票获得的最大利润。
1.动态规划
class Solution {
public:
int maxProfit(vector<int>& prices) {
if(prices.size() == 0) return 0;
vector<vector<int>> dp(prices.size(), vector<int> (5, 0));
dp[0][1] = -prices[0];
dp[0][3] = -prices[0];
for(int i = 1; i < prices.size(); i++){
dp[i][0] = dp[i - 1][0];
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]);
dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
}
return dp[prices.size() - 1][4];
}
};
188 买卖股票的最佳时机 IV
思路：
maxProfit 函数：输入一个整数 k 和一个整数数组 prices，返回最多进行 k 次交易能够获得的最大利润。
main 函数：该函数在代码中没有给出，但是我们可以将其作为程序的入口点，用于接受输入、调用 maxProfit 函数，并输出结果。
dp 数组：该数组是用来保存动态规划状态的，其维度为 (prices.size(), 2 * k + 1)，表示在每一天和进行了多少次交易的情况下能够获得的最大利润。
初始化 dp 数组：在 dp 数组中，我们需要初始化每一天的第 1, 3, 5, ..., 2k-1 个状态，因为这些状态表示在进行交易的过程中持有股票的状态。这些状态的初始值为 -prices[0]，表示在第一天购买股票的情况下的最大利润。
状态转移：对于每一天 i 和进行了 j 次交易的情况，我们需要分别计算出在该天结束时持有股票和不持有股票的最大利润，然后更新 dp 数组中的值。具体来说，我们可以通过以下公式计算：
dp[i][j+1] = max(dp[i-1][j+1], dp[i-1][j]-prices[i])，表示在第 i 天结束时，已经进行了 j 次交易，并且持有股票的最大利润。
dp[i][j+2] = max(dp[i-1][j+2], dp[i-1][j+1]+prices[i])，表示在第 i 天结束时，已经进行了 j 次交易，并且不持有股票的最大利润。返回结果：最后，我们需要返回 dp[prices.size() - 1][2 * k]，表示在最后一天结束时，已经进行了 2 * k 次交易，并且不持有股票的最大利润。
1.动态规划
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
if(prices.size() == 0) return 0;
vector<vector<int>> dp(prices.size(), vector<int>(2 * k + 1, 0));
for(int j = 1; j < 2 * k; j += 2){
dp[0][j] = -prices[0];
}
for(int i = 1; i < prices.size(); i++){
for(int j = 0; j < 2 * k - 1; 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][2 * k];
}
};
