337. 打家劫舍 III

港控/mmm° 2022-11-26 09:57 114阅读 0赞

# 题目： #

[337. 打家劫舍 III][337. _ III]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70]

# 题解：动态规划 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 1]

## 1. 解释一： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 2]

root[0] = Math.max(rob(root.left)[0], rob(root.left)[1]) + Math.max(rob(root.right)[0], rob(root.right)[1])
    root[1] = rob(root.left)[0] + rob(root.right)[0] + root.val;

## 2. 解释二： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 3]

## 3. 解释三： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 4]

# 代码：动态规划 #

public class code337 { 
    
        // 树的后序遍历
    
        public static int rob(TreeNode root) { 
            // 计算当前节点偷与不偷所能获得收益，结果存在数组res中
            int res[] = dfs(root);
            // 根据题意可知需取其中最大的
            return Math.max(res[0], res[1]);
        }
    
        public static int[] dfs(TreeNode root)
        { 
            // 如果当前节点为空节点，则其结果为0
            if(root == null)
            { 
                int temp[] = {  0, 0 };
                return temp;
            }
            // 分类讨论的标准是：当前结点偷或者不偷
            // 由于需要后序遍历，所以先计算左右子结点，然后计算当前结点的状态值
    
            // 计算当前节点左儿子偷与不偷所能获得的收益
            int left[] = dfs(root.left);
            // 计算当前节点右儿子偷与不偷所能获得的收益
            int right[] = dfs(root.right);
    
            // dp[0]：以当前 node 为根结点的子树能够偷取的最大价值，规定 node 结点不偷
            // dp[1]：以当前 node 为根结点的子树能够偷取的最大价值，规定 node 结点偷
            int dp[] = new int[2];
    
            // 不偷，下家可偷可不偷，取决于收益大小
            // 不偷当前节点所能获得的最大收益 = 左儿子所能获得的最大收益 + 右儿子所能获得的最大收益
            // 儿子所能获得最大收益为：max（不偷当前儿子所能获得最大收益，偷当前儿子所能获得最大收益）
            dp[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
            // 偷，下家就不能偷了
            // 偷当前节点所能获得的最大收益= 偷当前节点的钱 + 不偷左儿子所获得的钱 +不偷右儿子所获得的钱
            dp[1] = root.val + left[0] + right[0];
    
            return dp;
        }
    
        public static void main(String[] args) { 
            Integer nums1[] = {  3, 2, 3, null, 3, null, 1 };
            TreeNode root1 = ConstructTree.constructTree(nums1);
            TreeOperation.show(root1);
    
            System.out.println("***************************************");
    
            int res1 = rob(root1);
            System.out.println(res1);
    
            System.out.println("***************************************");
    
            Integer nums2[] = {  3, 4, 5, 1, 3, null, 1 };
            TreeNode root2 = ConstructTree.constructTree(nums2);
            TreeOperation.show(root2);
    
            System.out.println("***************************************");
    
            int res2 = rob(root2);
            System.out.println(res2);
    
            System.out.println("***************************************");
    
            Integer nums3[] = {  2, 1, 3, null, 4 };
            TreeNode root3 = ConstructTree.constructTree(nums3);
            TreeOperation.show(root3);
    
            System.out.println("***************************************");
    
            int res3 = rob(root3);
            System.out.println(res3);
    
            System.out.println("***************************************");
    
        }
    }

# 参考： #

1.  [打家劫舍 III][III]
2.  [三种方法解决树形动态规划问题-从入门级代码到高效树形动态规划代码实现][-]
3.  [树形 dp 入门问题（理解「无后效性」和「后序遍历」）][dp]
4.  [通用思路团灭打家劫舍问题][Link 1]
5.  [三种解法+多图演示 337. 打家劫舍 III][337. _ III 1]
6.  [337. 打家劫舍 III][337. _ III 2]

[337. _ III]: https://leetcode-cn.com/problems/house-robber-iii/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70]: /images/20221124/06aedc7afa5b4164aaac70850cdab99e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 1]: /images/20221124/06647d463967498386be3df4aa36080f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 2]: /images/20221124/23d87a4f17184c0e9dee04c828fad546.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 3]: /images/20221124/3c797f7f8cdf46979de454c53b91dd70.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 4]: /images/20221124/86103fe426f042a38ea077c4cdd2a4a6.png
[III]: https://leetcode-cn.com/problems/house-robber-iii/solution/da-jia-jie-she-iii-by-leetcode-solution/
[-]: https://leetcode-cn.com/problems/house-robber-iii/solution/san-chong-fang-fa-jie-jue-shu-xing-dong-tai-gui-hu/
[dp]: https://leetcode-cn.com/problems/house-robber-iii/solution/shu-xing-dp-ru-men-wen-ti-by-liweiwei1419/
[Link 1]: https://leetcode-cn.com/problems/house-robber-iii/solution/tong-yong-si-lu-tuan-mie-da-jia-jie-she-wen-ti-b-2/
[337. _ III 1]: https://leetcode-cn.com/problems/house-robber-iii/solution/san-chong-jie-fa-duo-tu-yan-shi-337-da-jia-jie-she/
[337. _ III 2]: https://leetcode-cn.com/problems/house-robber-iii/solution/337-da-jia-jie-she-iii-by-ming-zhi-shan-you-m9rf-2/