leetcode 337. House Robber III | 337. 打家劫舍 III（树形dp；什么情况下dp需要强制包含当前元素？）-蒲公英云

leetcode 337. House Robber III | 337. 打家劫舍 III（树形dp；什么情况下dp需要强制包含当前元素？）

题目

https://leetcode.com/problems/house-robber-iii/
在这里插入图片描述

思考：什么情况下 dp 需要强制包含当前元素？

dp 过程中，需要包含当前元素 的例子：

leetcode 322. Coin Change | 322. 零钱兑换（动态规划）
leetcode 300. Longest Increasing Subsequence | 300. 最长递增子序列（动态规划）
算法设计与分析：0-1背包问题（动态规划）

dp 过程中，不需要包含当前元素 的例子：

leetcode 198. 打家劫舍（动态规划）
leetcode 213. House Robber II | 213. 打家劫舍 II（动态规划）

当问题类似于 前缀和问题、背包问题 的时候，也就是 对 dp 数组的访问是按照索引进行随机访问 的情况下，需要在每一个状态上包含元素本身信息，所以这种情况下 通常强制包含当前元素。

而当问题类似于 打家劫舍 问题的时候，结果与被遍历序列的前后顺序有关，对 dp 数组的访问只涉及到 i-1, i-2 等这些有限个数的相邻下标（假设当前元素下标为 i），不需要对前面的 dp 数组进行随机访问，这时不需要存储每一个状态下的元素本身信息，通常不用强制包含当前元素。

题解

参考了：https://leetcode.com/problems/house-robber-iii/discuss/79330/Step-by-step-tackling-of-the-problem 的开头，有了点思路，后面自己写的。

可以看作是一个树形 dp 问题，也可以参考：左神算法：找到二叉树中的最大搜索二叉子树（树形dp套路，Java版）

class Solution { 
    public int rob(TreeNode root) { 
        if (root == null) return 0;
        rob(root.left);
        rob(root.right);
        int l, r, ll, lr, rl, rr;
        l = r = ll = lr = rl = rr = 0;
        if (root.left != null) { 
            l = root.left.val;
            if (root.left.left != null) { 
                ll = root.left.left.val;
            }
            if (root.left.right != null) { 
                lr = root.left.right.val;
            }
        }
        if (root.right != null) { 
            r = root.right.val;
            if (root.right.left != null) { 
                rl = root.right.left.val;
            }
            if (root.right.right != null) { 
                rr = root.right.right.val;
            }
        }
        // root.val 存储【偷或不偷】当前元素时的最大值
        root.val = Math.max(root.val + ll + lr + rl + rr, l + r);
        return root.val;
    }
}