【LeetCode笔记】337.打家劫舍III（Java、树型动态规划）

题目描述

• 这年头当个小偷&＃xff0c;都得会 dp 和二叉树了
• 和前面的 I & II 有点不同&＃xff0c;这次直接换了数据结构&＃xff0c;写树来了。&＃xff08;之后不会是图吧&＃xff09;
• 很厉害&＃xff0c;第一次接触到树型的dp&＃xff0c;一听就特别不同凡响
  

思路 & 代码

• 返回值分成两部分&＃xff0c;一个是当前 root 偷了的情况&＃xff0c;一个是没偷的情况
• 状态转移方程、最优子结构、边界见代码
• 时间复杂度 O(n)&＃xff0c;空间复杂度 O(n)

/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val &＃61; val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val &＃61; val;* this.left &＃61; left;* this.right &＃61; right;* }* }*/
class Solution {public int rob(TreeNode root) {// 0&＃xff1a;当前结点未取 1&＃xff1a;当前结点取了int[] result &＃61; forRob(root);return Math.max(result[0], result[1]);}int[] forRob(TreeNode root){// 边界if(root &＃61;&＃61; null){return new int[2];}int[] result &＃61; new int[2];// 最优子结构int[] right &＃61; forRob(root.right);int[] left &＃61; forRob(root.left);// 状态转移方程// root 没偷的情况&＃xff1a;左右结点可偷&＃xff0c;也可不偷result[0] &＃61; Math.max(left[0], left[1]) &＃43; Math.max(right[0], right[1]);// root 偷了的情况&＃xff1a;左右结点一定不偷result[1] &＃61; root.val &＃43; left[0] &＃43; right[0];return result;}
}


更新版

• 自底向上&＃xff0c;状态转移方程是重点&＃xff0c;思路可以看上面代码的注释。

class Solution {public int rob(TreeNode root) {int[] ans &＃61; robTree(root);return Math.max(ans[0], ans[1]);}public int[] robTree(TreeNode root) {if(root &＃61;&＃61; null) {return new int[]{0, 0};}int[] left &＃61; robTree(root.left);int[] right &＃61; robTree(root.right);int[] now &＃61; new int[2];now[0] &＃61; Math.max(left[0], left[1]) &＃43; Math.max(right[0], right[1]);now[1] &＃61; root.val &＃43; left[0] &＃43; right[0];return now;}
}