算法-动态规划-打家劫舍3

╰半夏微凉° 2023-03-06 05:03 23阅读 0赞

# 算法-动态规划-打家劫舍3 #

# 1 题目概述 #

## 1.1 题目出处 ##

https://leetcode-cn.com/problems/house-robber-iii

## 1.2 题目描述 ##

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

# 2 动态规划 #

## 2.1 思路 ##

见代码注释。

## 2.2 代码 ##

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
    class Solution { 
        public int rob(TreeNode root) { 
            if(root == null){ 
                return 0;
            }
            // 需要分别考虑选本节点和不选本节点的两种情况
            // 选本节点时，最大金额取决于本节点金额加上不选左右子节点的最大金额
            // 而不选本节点时，最大金额计算就比较麻烦了，不一定选左右子节点就是最大金额
            // 所以这里必须要使用一个数组，分别记录选当前节点时的最大金额以及不选当前节点时的最大金额
    
            // 元素0代表选择本节点时的最大金额，元素1代表不选本节点时的最大金额
            int[] result = dfs(root);
    
            return Math.max(result[0], result[1]);
        }
    
        private int[] dfs(TreeNode root){ 
            // 元素0代表选择本节点时的最大金额，元素1代表不选本节点时的最大金额
            int[] result = new int[2];
            if(root == null){ 
                result[0] = 0;
                result[1] = 0;
                return result;
            }
    
            int[] l = dfs(root.left);
            int[] r = dfs(root.right);
            
            // 选择root时，最大金额就是root.val + 不选左右子节点时的最大金额
            result[0] = root.val + l[1] + r[1];
            // 而不选root时，最大金额为 Math.max(不选左子节点最大金额，选左子节点最大金额) 
            // + Math.max(不选右子节点最大金额，选右子节点最大金额)
            // 考虑 [4,1,null,2,null,3]这样的左斜二叉树，
            // 最大金额为7，就是直接选根节点4和尾节点3的和，跳过中间1和2
            // 而不是说选了4就必须选2才是最大！！！
    
            // 注意这和打家劫舍1和2中不同，那里面dp[i]表示选或不选i时的最大金额
            // 而这里的i节点的l[0]就表示包含了i节点值的最大金额了
            // 所以必须分开考虑！
            result[1] = Math.max(l[0], l[1]) + Math.max(r[0], r[1]);
            return result;
        }
    }

## 2.3 时间复杂度 ##

![在这里插入图片描述][20200805112320229.png]  
O(N)

*  每个元素都遍历一次

## 2.4 空间复杂度 ##

O(N)

*  递归

# 参考文档 #

*  [树形 dp 入门问题（理解「无后效性」和「后序遍历」）][dp]
 *  [三种方法解决树形动态规划问题-从入门级代码到高效树形动态规划代码实现][-]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70]: /images/20230208/12cb2bd2c3b14987a1059ceed7c97870.png
[20200805112320229.png]: /images/20230208/2dfbf38aeb7e4e58b75fb11a722d2608.png
[dp]: https://leetcode-cn.com/problems/house-robber-iii/solution/shu-xing-dp-ru-men-wen-ti-by-liweiwei1419/
[-]: https://leetcode-cn.com/problems/house-robber-iii/solution/san-chong-fang-fa-jie-jue-shu-xing-dong-tai-gui-hu/