算法精讲--动态规划（三）：树形DP与状态机模型
🚀 算法精讲–动态规划（三）：树形DP与状态机模型
📚 前情回顾：前两期咱们搞定 单序列DP和多维DP，今天解锁更带劲的玩法！建议先预习：337. 打家劫舍 III 和 122. 买卖股票的最佳时机 II
🌟 知识图谱
一、🌲 树形DP
1.1 打家劫舍III（337. 打家劫舍 III）
🔍 Step1：审题分析
- 核心约束 ：父子节点不能同时被偷
- 目标 ：二叉树结构中的最大偷窃金额
- 特殊边界 ：空树返回0
📐 Step2：方案设计
状态定义 ：
- int[2] res：res[0]不选当前节点，res[1]选当前节点
转移方程 ：
res[父][0] = max(左[0], 左[1]) + max(右[0], 右[1])
res[父][1] = 父.val + 左[0] + 右[0]
🚀 Step3：执行验证
class Solution {
public int rob(TreeNode root) {
int[] res = dfs(root);
return Math.max(res[0], res[1]);
}
private int[] dfs(TreeNode node) {
if (node == null) return new int[2];
int[] left = dfs(node.left);
int[] right = dfs(node.right);
int notPick = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
int pick = node.val + left[0] + right[0];
return new int[]{notPick, pick};
}
}
测试案例 ：
输入：root = [3,2,3,null,3,null,1]
输出：7（选根节点3、左子节点2的右子节点3、右子节点3的右子节点1）
🎯 Step4：总结优化（后序遍历）
// 优化点：省略显式存储左右子树状态
class Solution {
public int rob(TreeNode root) {
int[] res = postOrder(root);
return Math.max(res[0], res[1]);
}
private int[] postOrder(TreeNode node) {
if (node == null) return new int[2];
int[] left = postOrder(node.left);
int[] right = postOrder(node.right);
return new int[]{
Math.max(left[0], left[1]) + Math.max(right[0], right[1]),
node.val + left[0] + right[0]
};
}
}
优化解析 ：
- 空间复用 ：直接利用后序遍历返回值
- 时间复杂度 ：O(n)
- 逻辑精简 ：合并状态更新步骤
1.2 二叉树直径（543. 二叉树的直径）
🔍 Step1：审题分析
- 核心定义：直径是任意两节点间最长路径（边数）
- 关键发现：直径 = 左子树深度 + 右子树深度
- 特殊边界：空树或单节点时直径为0
📐 Step2：方案设计
🚀 Step3：执行验证
class Solution {
private int maxDiameter = 0;
public int diameterOfBinaryTree(TreeNode root) {
calculateDepth(root);
return maxDiameter;
}
// 显式存储每个节点的左右深度
private int calculateDepth(TreeNode node) {
if (node == null) return 0;
int leftDepth = calculateDepth(node.left);
int rightDepth = calculateDepth(node.right);
// 计算当前节点为根的直径
int currentDiameter = leftDepth + rightDepth;
maxDiameter = Math.max(maxDiameter, currentDiameter);
return Math.max(leftDepth, rightDepth) + 1;
}
}
测试案例：
输入：root = [1,2,3,4,5]
输出：3（路径4->2->1->3 或 5->2->1->3）
🎯 Step4：总结优化（逻辑融合）
class Solution {
int max = 0;
public int diameterOfBinaryTree(TreeNode root) {
depth(root);
return max;
}
// 将深度计算与直径统计融合
private int depth(TreeNode node) {
if (node == null) return 0;
int left = depth(node.left);
int right = depth(node.right);
max = Math.max(max, left + right); // 实时更新最大值
return Math.max(left, right) + 1;
}
}
优化解析：
- 去冗余存储：不再显式存储每个节点的左右深度
- 时间复杂度：O(n)（每个节点访问一次）
- 空间复杂度：O(h)（递归栈深度，h为树高）
1.3 监控二叉树
🔍 Step1：审题分析
- 监控规则：摄像头可覆盖自身、父节点、子节点
- 目标：最少摄像头覆盖所有节点
- 特殊边界：空树无需摄像头，单节点需1个摄像头
📐 Step2：方案设计
🚀 Step3：执行验证（显式状态）
class Solution {
int cameras = 0;
public int minCameraCover(TreeNode root) {
int rootStatus = dfs(root);
return rootStatus == 0 ? cameras + 1 : cameras;
}
// 0-未覆盖 1-已安装 2-已覆盖
private int dfs(TreeNode node) {
if (node == null) return 2;
int left = dfs(node.left);
int right = dfs(node.right);
if (left == 0 || right == 0) {
cameras++;
return 1;
}
if (left == 1 || right == 1) return 2;
return 0;
}
}
测试案例：
输入：root = [0,0,null,0,0]
输出：1（根节点安装摄像头即可覆盖所有节点）
🎯 Step4：总结优化（逻辑精简）
class Solution {
int res = 0;
public int minCameraCover(TreeNode root) {
return (dfs(root) == 0 ? 1 : 0) + res;
}
private int dfs(TreeNode node) {
if (node == null) return 2;
int left = dfs(node.left), right = dfs(node.right);
if (left == 0 || right == 0) {
res++;
return 1;
}
return (left == 1 || right == 1) ? 2 : 0;
}
}
优化解析：
- 状态合并：将根节点特殊判断合并到主逻辑中
- 代码精简：减少条件判断层级
- 贪心策略：优先在父节点安装以覆盖更多子节点
二、⚙️ 状态机模型
2.1 股票含冷冻期（309. 最佳买卖时机含冷冻期）
🔍 Step1：审题分析
- 交易规则：卖出后需等待一天才能买入
- 目标：获取最大利润
- 特殊边界：单日价格直接返回0
📐 Step2：方案设计
🚀 Step3：执行验证（三维DP）
class Solution {
public int maxProfit(int[] prices) {
int n = prices.length;
int[][][] dp = new int[n][2][2]; // [天数][是否持有][是否冷冻]
// 初始化
dp[0][1][0] = -prices[0];
for (int i = 1; i < n; i++) {
// 当前持有股票：昨天持有未卖出 或 今天买入（需确保非冷冻期）
dp[i][1][0] = Math.max(dp[i-1][1][0], dp[i-1][0][0] - prices[i]);
// 当前未持有且处于冷冻期：昨天卖出
dp[i][0][1] = dp[i-1][1][0] + prices[i];
// 当前未持有且非冷冻期：昨天未持有（可能是冷冻期结束或保持）
dp[i][0][0] = Math.max(dp[i-1][0][0], dp[i-1][0][1]);
}
return Math.max(dp[n-1][0][0], dp[n-1][0][1]);
}
}
🎯 Step4：总结优化（状态压缩）
class Solution {
public int maxProfit(int[] prices) {
int hold = -prices[0], cold = 0, not = 0;
for (int i = 1; i < prices.length; i++) {
int preHold = hold;
hold = Math.max(hold, not - prices[i]);
not = Math.max(not, cold);
cold = preHold + prices[i];
}
return Math.max(cold, not);
}
}
优化解析：
- 空间压缩：从 O(n) 降为 O(1)
- 状态合并：将三维状态压缩为三个变量
- 循环优化：直接遍历价格数组，无需维护完整DP表
2.2 买卖股票II（122. 最佳买卖时机 II）
🔍 Step1：审题分析
- 交易规则 ：允许无限次交易，当天可买卖
- 目标 ：最大化利润
- 关键发现 ：累积所有上涨波段收益
📐 Step2：方案设计
状态定义 ：
- hold：持有股票的最大收益
- notHold：未持有股票的最大收益
🚀 Step3：执行验证（二维DP）
class Solution {
public int maxProfit(int[] prices) {
int n = prices.length;
int[][] dp = new int[n][2];
dp[0][0] = 0;
dp[0][1] = -prices[0];
for (int i = 1; i < n; i++) {
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]);
}
return dp[n-1][0];
}
}
🎯 Step4：总结优化（滚动变量）
class Solution {
public int maxProfit(int[] prices) {
int hold = -prices[0], notHold = 0;
for (int i = 1; i < prices.length; i++) {
int preHold = hold;
hold = Math.max(hold, notHold - prices[i]);
notHold = Math.max(notHold, preHold + prices[i]);
}
return notHold;
}
}
优化解析 ：
- 空间压缩 ：从O(n)降为O(1)
- 状态转移 ：直接利用前序状态
- 计算优化 ：消除数组访问开销
三、📊 方法论对比表
| 问题类型 | 基础版复杂度 | 优化版复杂度 | 优化技巧 |
|---|---|---|---|
| 树形DP | O(n) / O(n) | O(n) / O(h) | 后序遍历 + 状态压缩 |
| 状态机模型 | O(n) / O(n) | O(n) / O(1) | 滚动变量法 + 状态合并 |
优化原则：
- 空间换时间：优先保证时间复杂度最优
- 状态精简：合并冗余状态，保留核心状态转移
- 遍历顺序：利用问题特性（如树的后序遍历顺序）
四、💡 思维训练
拓展问题：2246. 相邻字符不同的最长路径
提示：
- 维护每个节点的子节点中字符不同的最长路径
- 全局变量记录最大值
- 注意相邻节点字符不同的约束条件
五、📦 下期剧透
《动态规划（四）：背包九讲》
预习指南：
- 01背包经典题：分割等和子集
- 完全背包变形：零钱兑换II
- 多维约束题：一和零
复杂度预对比：
🌟 思维拓展：尝试用树形DP思想解决2246. 相邻字符不同的最长路径，答案下期揭晓！
📢 互动环节：你在树形DP中遇到过哪些坑？