leetCode 337. 打家劫舍 III 动态规划 房子都连成树了，偷不偷呢？ “树形dp“ （递归三部曲 + 动规五部曲）

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。

>>思路和分析

• 可以对一个节点 “偷” 与 “不偷” 得到的最大金钱 做记录，实时计算
• 动态规划就是使用状态转移容器来记录状态的变化，使用一个长度为2的数组，记录当前的节点 “偷” 与 “不偷” 所得到的最大金钱
• 在树上进行状态转移，利用递归三部曲 + 动规五部曲 

>>递归三部曲 + 动规五部曲

1.确定递归函数的 参数 和 返回值

返回值是一个长度为2的dp数组，用来记录节点 “偷” 与 “不偷” 得到的金钱

vector<int> robTree(TreeNode* cur) {
    ...
}

• dp[0] 记录 “不偷” 该节点所得到的最大金钱
• dp[1] 记录 “偷” 该节点所得到的最大金钱

常见疑惑(O_O)?长度为2的dp数组怎么标记树中的每个节点的状态呢？

【解惑】其实在递归的过程中，系统栈会保存每一层递归的参数~

2.确定终止条件

在遍历过程中，若是遇到空节点，无论 “偷” 还是 “不偷” 都是 0 ，所以直接返回 {0,0}。因为空节点的金钱收益为0。而这也相当于 dp 数组的初始化

if(cur == NULL) return vector<int>{0,0};

3.确定遍历顺序

• 明确使用后序遍历，因为需要通过递归函数的返回值来做下一步计算
• 通过递归左节点，可得到左节点 “偷” 和 “不偷” 的金钱
• 通过递归右节点，可得到右节点 “偷” 和 “不偷” 的金钱

4.确定单层递归的逻辑

• 若 “偷” 当前节点，那么左右孩子就 “不能偷” ，val1 = cur -> val + left[0] + right[0]；
• 若 “不偷” 当前节点，那么左右孩子就 “可以偷”，在左右孩子的 “偷” 和 “不偷” 记录中选一个最大的，即 val2 = max(left[0],left[1]) + max(right[0],right[1]);
• 最后当前节点的状态就是 {val2,val1}; （意味着 “不偷” 当前节点得到的最大金钱，“偷” 当前节点得到的最大金钱）

5.举例推导 dp 数组

最后max{result[0],result[1]}; 的返回值就是头结点偷得的最大金钱

class Solution {
public:
    // 长度为2的数组，0:不偷，1:偷
    vector<int> robTree(TreeNode* cur) {
        if(cur == NULL) return vector<int>{0,0};
        vector<int> left = robTree(cur->left);
        vector<int> right = robTree(cur->right); 
        // 偷 cur，那么就不能偷左右节点
        int val1 = cur->val + left[0] + right[0];
        // 不偷 cur，那么可以偷也可以不偷左右节点，则取较大的情况
        int val2 = max(left[0],left[1]) + max(right[0],right[1]);
        // cout << "{val2 ,  val1} :" << val2 << "," << val1 <
        return {val2,val1};
    }
 
    int rob(TreeNode* root) {
        vector<int> result = robTree(root);
        return max(result[0],result[1]);
    }
};

• 时间复杂度：O(n)，每个节点只遍历了一次
• 空间复杂度：O(log n)，算上递推系统栈的空间

参考和推荐文章、视频

代码随想录 (programmercarl.com)

动态规划，房间连成树了，偷不偷呢？| LeetCode：337.打家劫舍3_哔哩哔哩_bilibili

来自代码随想录的课堂截图：