198.打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
思路：
dp数组：dp[i]：考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]。dp[0] = nums[0]，dp[1] = max(nums[0], nums[1])
递推公式：dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
遍历顺序：从前往后遍历
213.打家劫舍II
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，能够偷窃到的最高金额。
思路：环状结构，偷了第一家就不能偷最后一家。那我们就只要比较：不偷第一家的时候 VS 不偷最后一家的时候 的偷窃的最高金额。
337.打家劫舍III
这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。
思路：在树上面做动态规划，不一定要按照原先的dp数组那样去做，就按照习惯的遍历树的方式做就好。
1. 定义一个二元素元组（也就是dp数组的概念）。分别代表：以当前节点为根节点，窃贼偷了当前节点 VS 不偷当前节点的最大收益。本题只要在二叉树的根节点取两者最大值即可。
2. 遍历顺序：当前节点的收益取决于左右子树。因此要先返回左右子树的元组。那这就是后序遍历了。
3. 后序遍历用迭代法难以处理，用递归法处理。基线条件，如果节点为空，返回（0，0）。递归条件，元组的两个元素取决于左右子节点的返回，详见代码。
以下是卡哥资料
今天就是打家劫舍的一天，这个系列不算难，大家可以一口气拿下。
198.打家劫舍
视频讲解：https://www.bilibili.com/video/BV1Te411N7SX
https://programmercarl.com/0198.%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8D.html
213.打家劫舍II
视频讲解：https://www.bilibili.com/video/BV1oM411B7xq
https://programmercarl.com/0213.%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8DII.html
337.打家劫舍III
视频讲解：https://www.bilibili.com/video/BV1H24y1Q7sY
https://programmercarl.com/0337.%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8DIII.html
