[Leetcode][第337题][JAVA][打家劫舍3][递归][动态规划]

阳光穿透心脏的1/2处 2023-03-06 05:19 2阅读 0赞

#### 【问题描述】\[中等\] ####

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

#### 【解答思路】 ####

###### 1. 动态规划 ######

**第 1 步：状态定义**  
dp\[node\]\[j\] ：这里 node 表示一个结点，以 node 为根结点的树，并且规定了 node 是否偷取能够获得的最大价值。

j = 0 表示 node 结点不偷取；  
j = 1 表示 node 结点偷取。  
**第 2 步： 推导状态转移方程**  
根据当前结点偷或者不偷，就决定了需要从哪些子结点里的对应的状态转移过来。

如果当前结点不偷，左右子结点偷或者不偷都行，选最大者；  
如果当前结点偷，左右子结点均不能偷。  
（状态转移方程的表述有点复杂，请大家直接看代码。）

**第 3 步： 初始化**  
一个结点都没有，空节点，返回 0，对应后序遍历时候的递归终止条件；

**第 4 步： 输出**  
在根结点的时候，返回两个状态的较大者。

**第 5 步： 思考优化空间**  
优化不了。  
**时间复杂度：O(N) 空间复杂度：O(N)**

public 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[]{ 0, 0};
            }
    
            // 分类讨论的标准是：当前结点偷或者不偷
            // 由于需要后序遍历，所以先计算左右子结点，然后计算当前结点的状态值
            int[] left = dfs(node.left);
            int[] right = dfs(node.right);
    
            // dp[0]：以当前 node 为根结点的子树能够偷取的最大价值，规定 node 结点不偷
            // dp[1]：以当前 node 为根结点的子树能够偷取的最大价值，规定 node 结点偷
            int[] dp = new int[2];
    
            dp[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
            dp[1] = node.val + left[0] + right[0];
            return dp;
        }
    }

###### 2. 递归 ######

使用爷爷、两个孩子、4 个孙子来说明问题  
首先来定义这个问题的状态  
爷爷节点获取到最大的偷取的钱数呢

1.  首先要明确相邻的节点不能偷，也就是爷爷选择偷，儿子就不能偷了，但是孙子可以偷
2.  二叉树只有左右两个孩子，一个爷爷最多 2 个儿子，4 个孙子  
    根据以上条件，我们可以得出单个节点的钱该怎么算  
    **4 个孙子偷的钱 + 爷爷的钱 VS 两个儿子偷的钱 哪个组合钱多，就当做当前节点能偷的最大钱数。这就是动态规划里面的最优子结构**  
    由于是二叉树，这里可以选择计算所有子节点

4 个孙子投的钱加上爷爷的钱如下  
int method1 = root.val + rob(root.left.left) + rob(root.left.right) + rob(root.right.left) + rob(root.right.right)  
两个儿子偷的钱如下  
int method2 = rob(root.left) + rob(root.right);  
挑选一个钱数多的方案则  
int result = Math.max(method1, method2);

**2.1暴力递归**

public int rob(TreeNode root) { 
        if (root == null) return 0;
    
        int money = root.val;
        if (root.left != null) { 
            money += (rob(root.left.left) + rob(root.left.right));
        }
    
        if (root.right != null) { 
            money += (rob(root.right.left) + rob(root.right.right));
        }
    
        return Math.max(money, rob(root.left) + rob(root.right));
    }

**2.2 记忆化递归**  
针对2.1中速度太慢的问题，经过分析其实现，我们发现爷爷在计算自己能偷多少钱的时候，同时计算了 4 个孙子能偷多少钱，也计算了 2 个儿子能偷多少钱。这样在儿子当爷爷时，就会产生重复计算一遍孙子节点。

于是乎我们发现了一个**动态规划的关键优化点**

我们这一步针对重复子问题进行优化，我们在做斐波那契数列时，使用的优化方案是记忆化，但是之前的问题都是使用数组解决的，把每次计算的结果都存起来，下次如果再来计算，就从缓存中取，不再计算了，这样就保证每个数字只计算一次。  
由于二叉树不适合拿数组当缓存，我们这次使用哈希表来存储结果，TreeNode 当做 key，能偷的钱当做 value

public int rob(TreeNode root) { 
    //hashmap 记忆化
        HashMap<TreeNode, Integer> memo = new HashMap<>();
        return robInternal(root, memo);
    }
    
    public int robInternal(TreeNode root, HashMap<TreeNode, Integer> memo) { 
        if (root == null) return 0;
        if (memo.containsKey(root)) return memo.get(root);
        int money = root.val;
    
        if (root.left != null) { 
            money += (robInternal(root.left.left, memo) + robInternal(root.left.right, memo));
        }
        if (root.right != null) { 
            money += (robInternal(root.right.left, memo) + robInternal(root.right.right, memo));
        }
        int result = Math.max(money, robInternal(root.left, memo) + robInternal(root.right, memo));
        ///！！！
        memo.put(root, result);
        return result;
    }

#### 【总结】 ####

###### 1. 动态规划流程 ######

第 1 步：设计状态  
第 2 步：状态转移方程  
第 3 步：考虑初始化  
第 4 步：考虑输出  
第 5 步：考虑是否可以状态压缩

###### 2.递归 递推公式要找准 后用记忆化搜索优化 这题不能用BFS，层次遍历不符合题解 ######

转载链接：https://leetcode-cn.com/problems/house-robber-iii/solution/san-chong-fang-fa-jie-jue-shu-xing-dong-tai-gui-hu/  
转载链接：https://leetcode-cn.com/problems/house-robber-iii/solution/shu-xing-dp-ru-men-wen-ti-by-liweiwei1419/

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]: /images/20230208/9db60ba0eed14eba92caa67d47fce9e1.png