代码随想录算法训练营19期第48天

198.打家劫舍  

视频讲解：动态规划，偷不偷这个房间呢？| LeetCode：198.打家劫舍_哔哩哔哩_bilibili

代码随想录  

初步思路：动态规划。

总结：

dp[i]：考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]

递归公式： dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);

用时：20分钟

 213.打家劫舍II  

视频讲解：动态规划，房间连成环了那还偷不偷呢？| LeetCode：213.打家劫舍II_哔哩哔哩_bilibili

代码随想录

初步思路：动态规划。

总结：

分别考虑2种情况：【1】包含首元素，不包含尾元素 【2】包含尾元素，不包含首元素

用时：30分钟

 337.打家劫舍III  

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

代码随想录

初步思路：动态规划 + 树的遍历。

总结：

【1】    要后序遍历，因为通过递归函数的返回值来做下一步计算
【2】    树形dp的入门题目
# dp数组（dp table）以及下标的含义：
          # 1. 下标为 0 记录 **不偷该节点** 所得到的的最大金钱
          # 2. 下标为 1 记录 **偷该节点** 所得到的的最大金钱

【3】    通过递归左节点，得到左节点偷与不偷的金钱。
【4】    通过递归右节点，得到右节点偷与不偷的金钱。
【5】      
        # 不偷当前节点, 偷子节点
        val_0 = max(left[0], left[1]) + max(right[0], right[1])
        # 偷当前节点, 不偷子节点
        val_1 = node.val + left[0] + right[0]

用时：45分钟