解题思路：
-
Base cases:
T[-1][k][0] = 0, T[-1][k][1] = -Infinity
T[i][0][0] = 0, T[i][0][1] = -InfinityRecurrence relations:
T[i][k][0] = max(T[i-1][k][0], T[i-1][k][1] + prices[i])
T[i][k][1] = max(T[i-1][k][1], T[i-1][k-1][0] - prices[i])
T[i][k][0] denotes the maximum profit at the end of the i-th day with at most k transactions with 0 stock in our hand after taking the action.
T[i][k][1] denotes the maximum profit at the end of the i-th day with at most k transactions with 1 stock in our hand after taking the action.
- Best Time to Buy and Sell Stock （121）
https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/ - Best Time to Buy and Sell Stock with Transaction Fee （714）
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/description/ - Best Time to Buy and Sell Stock with Cooldown (309)
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/description/ - Best Time to Buy and Sell Stock III （123）
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/description/ - Best Time to Buy and Sell Stock IV （188）
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/description/ - Best Time to Buy and Sell Stock II (122)
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/description/
Best Time to Buy and Sell Stock 代码：
class Solution {
public int maxProfit(int[] prices) {
int len = prices.length;
int T_i10 = 0, T_i11 = Integer.MIN_VALUE;
for(int i = 0; i < len; i++){
T_i10 = Math.max(T_i10, T_i11 + prices[i]);
T_i11 = Math.max(T_i11, -prices[i]);
}
return T_i10;
}
}
Best Time to Buy and Sell Stock with Transaction Fee 代码：
class Solution {
public int maxProfit(int[] prices, int fee) {
int T_ik0 = 0, T_ik1 = Integer.MIN_VALUE;
for(int i = 0; i < prices.length; i++){
int T_ik0_old = T_ik0;
T_ik0 = Math.max(T_ik0, T_ik1 + prices[i]);
T_ik1 = Math.max(T_ik1, T_ik0_old - prices[i] - fee);
}
return T_ik0;
}
}
Best Time to Buy and Sell Stock with Cooldown 代码：
class Solution {
public int maxProfit(int[] prices) {
int T_ik0 = 0, T_ik0_pre = 0, T_ik1 = Integer.MIN_VALUE;
for(int price: prices){
int T_ik0_old = T_ik0;
T_ik0 = Math.max(T_ik0, T_ik1 + price);
T_ik1 = Math.max(T_ik1, T_ik0_pre - price);
T_ik0_pre = T_ik0_old;
}
return T_ik0;
}
}
Best Time to Buy and Sell Stock III 代码：
class Solution {
public int maxProfit(int[] prices) {
int T_i10 = 0, T_i11 = Integer.MIN_VALUE, T_i20 = 0, T_i21 = Integer.MIN_VALUE;
for(int price : prices){
T_i20 = Math.max(T_i20, T_i21 + price);
T_i21 = Math.max(T_i21, T_i10 - price);
T_i10 = Math.max(T_i10, T_i11 + price);
T_i11 = Math.max(T_i11, - price);
}
return T_i20;
}
}
Best Time to Buy and Sell Stock IV 代码：
class Solution {
public int maxProfit(int k, int[] prices) {
if(k > prices.length){
int T_ik0 = 0, T_ik1 = Integer.MIN_VALUE;
for(int price : prices){
int T_ik0_old = T_ik0;
T_ik0 = Math.max(T_ik0, T_ik1 + price);
T_ik1 = Math.max(T_ik1, T_ik0_old - price);
}
return T_ik0;
}
int[] T_ik0 = new int[k + 1];
int[] T_ik1 = new int[k + 1];
Arrays.fill(T_ik1, Integer.MIN_VALUE);
for(int price : prices){
for(int i = k; i > 0; i--){
T_ik0[i] = Math.max(T_ik0[i], T_ik1[i] + price);
T_ik1[i] = Math.max(T_ik1[i], T_ik0[i - 1] - price);
}
}
return T_ik0[k];
}
}
Best Time to Buy and Sell Stock II 代码：
class Solution {
public int maxProfit(int[] prices) {
int T_i10 = 0, T_i11 = Integer.MIN_VALUE;
for(int price : prices){
int T_i10_old = T_i10;
T_i10 = Math.max(T_i10, T_i11 + price);
T_i11 = Math.max(T_i11, T_i10_old - price);
}
return T_i10;
}
}
