買賣股票系列
【leetcode】40-best-time-to-buy-and-sell-stock 力扣 121. 買賣股票的最佳時機(jī)
【leetcode】41-best-time-to-buy-and-sell-stock-ii 力扣 122. 買賣股票的最佳時機(jī) II
【leetcode】42-best-time-to-buy-and-sell-stock-iii 力扣 123. 買賣股票的最佳時機(jī) III
【leetcode】43-best-time-to-buy-and-sell-stock-iv 力扣 188. 買賣股票的最佳時機(jī) IV
【leetcode】44-best-time-to-buy-and-sell-stock-with-cooldown 力扣 309. 買賣股票的最佳時機(jī)包含冷凍期
【leetcode】45-best-time-to-buy-and-sell-stock-with-cooldown 力扣 714. 買賣股票的最佳時機(jī)包含手續(xù)費
開源地址
為了便于大家學(xué)習(xí)，所有實現(xiàn)均已開源紧唱。歡迎 fork + star~
188. 買賣股票的最佳時機(jī) IV
給你一個整數(shù)數(shù)組 prices 和一個整數(shù) k ，其中 prices[i] 是某支給定的股票在第 i 天的價格笆载。
設(shè)計一個算法來計算你所能獲取的最大利潤唆缴。你最多可以完成 k 筆交易鳍征。也就是說，你最多可以買 k 次面徽，賣 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 暖释。
提示：
1 <= k <= 100
1 <= prices.length <= 1000
0 <= prices[i] <= 1000
V1-dp 解法貫穿思路
和其他題目的關(guān)聯(lián)
如果 k > len / 2， 因為無論怎么波動墨吓，其實最多 len/2 個數(shù)值球匕，我們可以直接用 122 的無限次來通過部分案例。
如果 k = 1肛真，就是 T121 的解法谐丢。
思路
整體就是貫穿的 dp 解法爽航。
k次交易分為k次：
b1 第一次買入
s1 第一次賣出
b2 第二次買入
s2 第二次賣出
...
bk 第k次買入
sk 第k次賣出
初始化
b1, b2 ... bk 初始化為 -prices[0]
s1, s2, ..., sk 初始化為0
代碼
public int maxProfit(int[] prices) {
int b1 = -prices[0];
int b2 = -prices[0];
int s1 = 0;
int s2 = 0;
for(int i = 0; i < prices.length; i++) {
// 賣出第二筆 是否賣蚓让？
s2 = Math.max(s2, b2 + prices[i]);
// 買入第二筆 是否買？
b2 = Math.max(b2, s1 - prices[i]);
// 賣出第一筆 是否賣讥珍？
s1 = Math.max(s1, b1 + prices[i]);
// 買入第一筆 是否買历极？
b1 = Math.max(b1, - prices[i]);
}
return s2;
}
實現(xiàn)
/**
* 優(yōu)化思路：通過 DP 替代掉遞歸。
*
* @param prices 價格數(shù)組
* @return 結(jié)果
*/
public int maxProfit(int k, int[] prices) {
// k+1 是為了讓 k 和 下標(biāo)相同衷佃，-1 也可以趟卸。
int[] buy = new int[k + 1];
int[] sell = new int[k + 1];
// 初始化買入狀態(tài)為最小值，表示極小的初始損失
for (int i = 0; i <= k; i++) {
buy[i] = -prices[0];
}
// for-each 數(shù)組本身
for (int i = 1; i < prices.length; i++) {
// for-each k 次操作
for (int j = 1; j <= k; j++) {
// 賣出第 j 次 不賣 OR 賣出：當(dāng)前買入+介個
sell[j] = Math.max(sell[j], buy[j] + prices[i]);
// 買入第 j 次 不買 OR 買入=上一次-當(dāng)前
buy[j] = Math.max(buy[j], sell[j - 1] - prices[i]);
}
}
return sell[k];
}
評價
這一種解法其實非常容易理解氏义，也非常容易拓展锄列。
小結(jié)
完整的思路，其實 T123 的拓展是一個比較完整的解法惯悠。
參考資料
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/
