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

【问题描述】[中等]

【解答思路】

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;
    }
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

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));
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

【总结】

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/