【动态规划左右数组 0不偷1偷】 337 打家劫舍

题目

如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。 输入: [3,2,3,null,3,null,1] 3 / 2 3 \ \ 3 1 输出: 7 解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.

思路

后序遍历：需要先知道叶子节点的信息，才能决定父节点。 递归由下到上，回溯由上到下 res【】，有两个状态，0表示不偷，1表示偷，值表示当前的最大金额。 从子节点转移来的状态： 如果当前结点不偷，左右子结点偷或者不偷都行，选最大者； 如果当前结点偷，左右子结点均不能偷。

代码

public int rob(TreeNode root) { //每个元素有两个选择，0表示不偷，1表示偷。当前数组值表示目前的最大金额 int []res = dfs(root); return Math.max(res[0],res[1]); } public int [] dfs(TreeNode root){ if(root==null) return new int[]{0,0}; int []left = dfs(root.left); int []right = dfs(root.right); int []res = new int[2]; res[0] = Math.max(left[0],left[1])+Math.max(right[0],right[1]); res[1] = root.val+left[0]+right[0]; return res; }