1.买卖股票的最佳时机含冷冻期
每次买完之后要等一天才能继续交易
相对于2,简单修改了状态转移方程 和 增加了base case2(根据最基础的状态转移方程推出来)
// 原始版本
int maxProfit_with_cool(int[] prices) {
int n = prices.length;
int[][] dp = new int[n][2];
for (int i = 0; i < n; i++) {
if (i - 1 == -1) {
// base case 1
dp[i][0] = 0;
dp[i][1] = -prices[i];
continue;
}
if (i - 2 == -1) {
// base case 2
dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
// i - 2 小于 0 时根据状态转移方程推出对应 base case
dp[i][1] = Math.max(dp[i-1][1], -prices[i]);
// dp[i][1]
// = max(dp[i-1][1], dp[-1][0] - prices[i])
// = max(dp[i-1][1], 0 - prices[i])
// = max(dp[i-1][1], -prices[i])
continue;
}
dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
dp[i][1] = Math.max(dp[i-1][1], dp[i-2][0] - prices[i]);
}
return dp[n - 1][0];
}
// 空间复杂度优化版本
int maxProfit_with_cool(int[] prices) {
int n = prices.length;
int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;
int dp_pre_0 = 0; // 代表 dp[i-2][0]
for (int i = 0; i < n; i++) {
int temp = dp_i_0;
dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
dp_i_1 = Math.max(dp_i_1, dp_pre_0 - prices[i]);
dp_pre_0 = temp;
}
return dp_i_0;
}
2.买卖股票的最佳时机含手续费
注意base case都是由状态转移方程推出来的,转移方程改变后 base case 也要做出对应改变
// 原始版本
int maxProfit_with_fee(int[] prices, int fee) {
int n = prices.length;
int[][] dp = new int[n][2];
for (int i = 0; i < n; i++) {
if (i - 1 == -1) {
// base case
dp[i][0] = 0;
dp[i][1] = -prices[i] - fee;
// dp[i][1]
// = max(dp[i - 1][1], dp[i - 1][0] - prices[i] - fee)
// = max(dp[-1][1], dp[-1][0] - prices[i] - fee)
// = max(-inf, 0 - prices[i] - fee)
// = -prices[i] - fee
continue;
}
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i] - fee);
}
return dp[n - 1][0];
}
// 空间复杂度优化版本
int maxProfit_with_fee(int[] prices, int fee) {
int n = prices.length;
int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
int temp = dp_i_0;
dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
dp_i_1 = Math.max(dp_i_1, temp - prices[i] - fee);
}
return dp_i_0;
}