123.买卖股票的最佳时机III
题目链接：123.买卖股票的最佳时机III
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
**注意：**你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
文章讲解/视频讲解：https://programmercarl.com/0123.%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E7%9A%84%E6%9C%80%E4%BD%B3%E6%97%B6%E6%9C%BAIII.html
思路与实现
设置二维dp数组，其中第二维度大小为4，对应四种状态：dp[i][0]表示持有且未卖出，dp[i][1]表示未持有且卖出一次，dp[i][2]表示持有且卖出一次，dp[i][3]表示未持有且卖出两次，它们之间的递推式为：
dp[i][0] = max(dp[i - 1][0], -prices[i]);
dp[i][1] = max(dp[i - 1][1], dp[i][0] + prices[i]);
dp[i][2] = max(dp[i - 1][2], dp[i][1] - prices[i]);
dp[i][3] = max(dp[i - 1][3], dp[i][2] + prices[i]);
初始的赋值为：
dp[0][0] = -prices[0];
dp[0][1] = 0;
dp[0][2] = -prices[0];
dp[0][3] = 0;
遍历顺序还是从左到右，按照上述思路，代码如下：
class Solution {
public:
int maxProfit(vector<int>& prices) {
if(prices.size() == 1) return 0;
vector<vector<int>> dp(prices.size(), vector<int>(4, 0));
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
题目链接：188.买卖股票的最佳时机IV
给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。
**注意：**你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
文章讲解/视频讲解：https://programmercarl.com/0188.%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E7%9A%84%E6%9C%80%E4%BD%B3%E6%97%B6%E6%9C%BAIV.html
思路与实现
这道题是上一道题的扩展，上一道题相当于这里k = 2的特殊情况。同样设置二维dp数组，其中第二维的大小为2 * k，对应2 * k种状态：dp[i][2 * k]代表持有且卖出k - 1次，dp[i][2 * k + 1]代表持有且卖出k次。代码为：
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
if(prices.size() == 1) return 0;
vector<vector<int>> dp(prices.size(), vector<int>(2 * k, 0));
for(int i = 0;i<k;i++){
dp[0][2 * i] = -prices[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]);
for(int j = 1;j<k;j++){
dp[i][2 * j] = max(dp[i - 1][2 * j], dp[i - 1][2 * j - 1] - prices[i]);
dp[i][2 * j + 1] = max(dp[i - 1][2 * j + 1], dp[i - 1][2 * j] + prices[i]);
}
}
return dp[prices.size() - 1][2 * k - 1];
}
};
