AlgoPressAppearance
0188-买卖股票的最佳时机IV
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv
给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1：
输入：k = 2, prices = [2,4,1]
输出：2
解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
示例 2：
输入：k = 2, prices = [3,2,6,5,0,3]
输出：7
解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。
提示：
- 0 <= k <= 100
- 0 <= prices.length <= 1000
- 0 <= prices[i] <= 1000
思路
计算 min 最小值，然后计算利润，循环 k 次，记录下可以后面次数的最小值，在累计利润到最后一次的利润中。
参考代码
csharp
public class Solution{
public int MaxProfit(int k, int[] prices){
if(prices.Length == 0 || k == 0){
return 0;
}
int[] mins = new int[k];
for(int i=0; i<mins.Length; i++){
mins[i] = prices[0];
}
int[] profits = new int[k];
for(int i = 1; i < prices.Length; i++){
//第一次交易
mins[0] = Math.Min(mins[0],prices[i]);
profits[0] = Math.Max(profits[0],prices[i] - mins[0]);
// 后面几次交易基于第一次的基础
for(int j=1; j<k; j++){
mins[j] = Math.Min(mins[j],prices[i] - profits[j-1]); //重点：扣去上一次交易的利润
profits[j] = Math.Max(profits[j], prices[i] - mins[j]);
}
}
return profits[k-1];
}
}
复习：20220515，强行记住
csharp
public class Solution {
public int MaxProfit(int k, int[] prices) {
if(prices.Length == 0 || k == 0){
return 0;
}
//定义买卖利润数组
int[] buy = new int[k];
int[] sell = new int[k];
//填充默认值
Array.Fill(buy,-prices[0]);
Array.Fill(sell,0);
//状态转移，累计利润到下一次的sell
for(int i=1; i<prices.Length; i++){
buy[0] = Math.Max(buy[0],-prices[i]);
sell[0] = Math.Max(sell[0],prices[i] + buy[0]);
//循环合并利润
for(int j=1;j<k;j++){
buy[j] = Math.Max(buy[j],sell[j-1] - prices[i]);
sell[j] = Math.Max(sell[j],prices[i] + buy[j]);
}
}
return sell[k-1];
}
}