状态机 DP
大约 5 分钟
状态机 DP
一般定义 f[i][j] 表示前缀 a[:i] 在状态 j 下的最优值。一般 j 都很小。代表题目是「买卖股票」系列。
| 题目 | 难度 | |
|---|---|---|
| 122. 买卖股票的最佳时机 II | 中等 | 不限交易次数 |
| 309. 买卖股票的最佳时机含冷冻期 | 中等 | dfs(n-2) |
| 714. 买卖股票的最佳时机含手续费 | 中等 | +fee |
| 188. 买卖股票的最佳时机 IV | 困难 | 至多交易 k 次 |
| 121. 买卖股票的最佳时机 | 简单 | k=1 |
| 123. 买卖股票的最佳时机 III | 困难 | k=2 |
122. 买卖股票的最佳时机 II
import java.util.Arrays;
public class Solution122 {
private int[] prices;
private int[][] memo;
public int maxProfit(int[] prices) {
this.prices = prices;
int n = prices.length;
memo = new int[n][2];
for (int i = 0; i < n; i++) {
Arrays.fill(memo[i], -1);
}
return dfs(n - 1, 0);
}
// dfs(i, 0) 表示到第 i 天结束时，未持有股票的最大利润
// dfs(i, 1) 表示到第 i 天结束时，持有股票的最大利润
// 第 i-1 天结束就是第 i 天的开始
private int dfs(int i, int hold) {
if (i < 0) {
if (hold == 1) return (int) -1e9;
return 0;
}
if (memo[i][hold] != -1) return memo[i][hold];
int res;
if (hold == 1) res = Math.max(dfs(i - 1, 1), dfs(i - 1, 0) - prices[i]);
else res = Math.max(dfs(i - 1, 0), dfs(i - 1, 1) + prices[i]);
return memo[i][hold] = res;
}
}309. 买卖股票的最佳时机含冷冻期
import java.util.Arrays;
public class Solution309 {
private int[] prices;
private int[][] memo;
public int maxProfit(int[] prices) {
this.prices = prices;
int n = prices.length;
memo = new int[n][2];
for (int i = 0; i < n; i++) {
Arrays.fill(memo[i], -1);
}
return dfs(n - 1, 0);
}
private int dfs(int i, int hold) {
if (i < 0) {
if (hold == 1) return (int) -1e9;
return 0;
}
if (memo[i][hold] != -1) return memo[i][hold];
int res;
if (hold == 1) res = Math.max(dfs(i - 1, 1), dfs(i - 2, 0) - prices[i]);
else res = Math.max(dfs(i - 1, 0), dfs(i - 1, 1) + prices[i]);
return memo[i][hold] = res;
}
}714. 买卖股票的最佳时机含手续费
import java.util.Arrays;
public class Solution714 {
private int[] prices;
private int fee;
private int[][] memo;
public int maxProfit(int[] prices, int fee) {
this.prices = prices;
this.fee = fee;
int n = prices.length;
memo = new int[n][2];
for (int i = 0; i < n; i++) {
Arrays.fill(memo[i], -1);
}
return dfs(n - 1, 0);
}
private int dfs(int i, int hold) {
if (i < 0) {
if (hold == 1) return (int) -1e9;
return 0;
}
if (memo[i][hold] != -1) return memo[i][hold];
int res;
if (hold == 1) res = Math.max(dfs(i - 1, 1), dfs(i - 1, 0) - prices[i] - fee);
else res = Math.max(dfs(i - 1, 0), dfs(i - 1, 1) + prices[i]);
return memo[i][hold] = res;
}
}188. 买卖股票的最佳时机 IV
import java.util.Arrays;
public class Solution188 {
private int[] prices;
private int[][][] memo;
public int maxProfit(int k, int[] prices) {
this.prices = prices;
int n = prices.length;
memo = new int[n][k + 1][2];
for (int i = 0; i < n; i++) {
for (int j = 0; j < k + 1; j++) {
Arrays.fill(memo[i][j], -1);
}
}
return dfs(n - 1, k, 0);
}
// dfs(i, 0) 表示到第 i 天结束时完成至多 j 笔交易，未持有股票的最大利润
// dfs(i, 1) 表示到第 i 天结束时完成至多 j 笔交易，持有股票的最大利润
// 第 i-1 天结束就是第 i 天的开始
private int dfs(int i, int j, int hold) {
if (j < 0) return (int) -1e9;
if (i < 0) {
if (hold == 1) return (int) -1e9;
return 0;
}
if (memo[i][j][hold] != -1) return memo[i][j][hold];
int res;
if (hold == 1) res = Math.max(dfs(i - 1, j, 1), dfs(i - 1, j - 1, 0) - prices[i]);
else res = Math.max(dfs(i - 1, j, 0), dfs(i - 1, j, 1) + prices[i]);
return memo[i][j][hold] = res;
}
}（全文完）