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

布满荆棘的人生 2023-01-23 13:51 59阅读 0赞

## 题目 ##

[https://leetcode.com/problems/house-robber-iii/][https_leetcode.com_problems_house-robber-iii]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

--------------------

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

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

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

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

*  [leetcode 198. 打家劫舍（动态规划）][leetcode 198.]
 *  [leetcode 213. House Robber II | 213. 打家劫舍 II（动态规划）][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][https_leetcode.com_problems_house-robber-iii_discuss_79330_Step-by-step-tackling-of-the-problem] 的开头，有了点思路，后面自己写的。

可以看作是一个树形 dp 问题，也可以参考：[左神算法：找到二叉树中的最大搜索二叉子树（树形dp套路，Java版）][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;
        }
    }

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

[https_leetcode.com_problems_house-robber-iii]: https://leetcode.com/problems/house-robber-iii/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20221004/d180a5a84b55426e8fa3b849cb58737a.png
[leetcode 322. Coin Change _ 322.]: https://blog.csdn.net/sinat_42483341/article/details/118672518
[leetcode 300. Longest Increasing Subsequence _ 300.]: https://blog.csdn.net/sinat_42483341/article/details/118487526
[0-1]: https://blog.csdn.net/sinat_42483341/article/details/89456491
[leetcode 198.]: https://blog.csdn.net/sinat_42483341/article/details/107534093
[leetcode 213. House Robber II _ 213. _ II]: https://blog.csdn.net/sinat_42483341/article/details/117898647
[https_leetcode.com_problems_house-robber-iii_discuss_79330_Step-by-step-tackling-of-the-problem]: https://leetcode.com/problems/house-robber-iii/discuss/79330/Step-by-step-tackling-of-the-problem
[dp_Java]: https://blog.csdn.net/sinat_42483341/article/details/111357131
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20221004/6d46d1106cf540cb9f063ae8ba3a5209.png