免费数据源网站免费加客源
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分钟