给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格，和一个整型 k 。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
解题思路：动态规划
(1) 定义dp数组
我们使用第一维来定义天数，第二维定义状态（具体来说：0表示持有股票，1表示不持有股票），第三维定义买卖次数。
例如，dp[2][1][3]表示：前2天（包括第2天）不持有股票，且买卖进行了三次的最大利润。
(2) 状态转移方程
当经过了 i - 1 天后，第 i 天：
● 持有股票 dp[i][0][k] = max(dp[i-1][0][k], dp[i-1][1][k-1] - prices[i])
● 没有股票 dp[i][1][k] = max(dp[i-1][1][k], dp[i-1][0][k] + prices[i])
⭕ 注意：
● 持有股票的时候，假设当天买入，那么第k次买入，需要考虑【没有股票的第k-1次】的最大利润
● 没有股票的时候，假设当天卖出，那么第k次卖出，需要考虑【持有股票的第k次】的最大利润
（因为只有第k次买了，才能进行第k次卖！！！）
(3) 初始化
● 对于持有股票来说，除了第0次，无论多少次的买入，都应该是dp[0][0][k] = -prices[0]（k≠0）
● 对于没有股票来说，无论多少次卖出，都应该是dp[0][1][k] = 0
(4) 遍历顺序
从前到后
(5) 举例：略。
class Solution {
public int maxProfit(int k, int[] prices) {
// dp[i][j][k]
// 第一维度：前 i 天（包括第 i 天）
// 第二维度：0表示持有股票，1表示没有持有股票
// 第三维度：k次交易
int[][][] dp = new int[prices.length][2][k+1];
// 初始化
for(int i=1; i<=k; i++){
dp[0][0][i] = -prices[0];
}
for(int i=1; i<prices.length; i++){
for(int j=1; j<=k; j++){
dp[i][0][j] = Math.max(dp[i-1][0][j], dp[i-1][1][j-1] - prices[i]);
dp[i][1][j] = Math.max(dp[i-1][1][j], dp[i-1][0][j] + prices[i]);
}
}
return dp[prices.length-1][1][k];
}
}
当k=2时，限定了只能进行两次买卖：
123. 买卖股票的最佳时机 III - 力扣（LeetCode）
class Solution {
public int maxProfit(int[] prices) {
// dp[i][j][m]：
// 第一维度：前 i 天（包括第 i 天）
// 第二维度：j=0 表示持有股票，j=1 表示没有持有股票
// 第三维度：m 表示买卖次数
int[][][] dp = new int[prices.length][2][3];
dp[0][0][0] = 0;
dp[0][0][1] = -prices[0];
dp[0][0][2] = -prices[0];
dp[0][1][0] = 0;
dp[0][1][1] = 0;
dp[0][1][2] = 0;
for(int i=1; i<prices.length; i++){
dp[i][0][0] = dp[i-1][0][0]; // 可以省略
dp[i][0][1] = Math.max(dp[i-1][0][1], dp[i-1][1][0] - prices[i]); // 可以省略为 Math.max(dp[i-1][0][1], - prices[i]);
dp[i][0][2] = Math.max(dp[i-1][0][2], dp[i-1][1][1] - prices[i]);
dp[i][1][0] = dp[i-1][1][0]; // 可以省略
dp[i][1][1] = Math.max(dp[i-1][1][1], dp[i-1][0][1] + prices[i]);
dp[i][1][2] = Math.max(dp[i-1][1][2], dp[i-1][0][2] + prices[i]);
}
// 找到0-m笔最大的利润
int result = 0;
for(int i=0; i<3; i++){
result = Math.max(dp[prices.length-1][1][i], result);
}
return result;
}
}
● 另一种思路，就是划分两个区间（买卖两次股票，所以一个股票一个区间，同时只能持有一只股票，即区间不能重叠）：
class Solution {
public int maxProfit(int[] prices) {
int dp[] = new int[prices.length]; // dp[i]：从第0天到第i天为止，可以获得一次买卖股票的最大利润
dp[0] = 0;
int min = prices[0];
for(int i=1; i<prices.length; i++){
if(prices[i] < min) min = prices[i];
dp[i] = Math.max(dp[i-1], prices[i] - min);
}
int dp2[] = new int[prices.length]; // dp2[i]：从第i天到第price.length-1天，可以获得的一次买卖股票的最大利润
dp2[prices.length-1] = 0;
int max = prices[prices.length-1];
for(int i=prices.length-2; i>=0; i--){
if(prices[i] > max) max = prices[i];
dp2[i] = Math.max(dp2[i+1], max-prices[i]);
}
int result = 0;
for(int i=0; i<prices.length; i++){
int tmp = dp[i] + dp2[i];
if(tmp > result) result = tmp;
}
return result;
}
}
