状态机 DP
2025年3月2日大约 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; } }（全文完）