打家劫舍

  1. 给定一个数组，求数组中不相邻元素的最大和。
  2. https://leetcode-cn.com/problems/house-robber/
  3. 简单动态规划

打家劫舍Ⅱ

  1. 数组头和数组尾被视为相邻，求这种情况下数组中不相邻元素的最大和。
  2. https://leetcode-cn.com/problems/house-robber-ii/
  3. 思路就是转换为上一个问题，难点在于怎么转换
    • 去头或去尾，即头不抢或尾不抢； 然后比较这两种情况的结果大小即可。
    • 我最开始想的是考虑头的两种情况：抢或不抢；但是如果头元素被抢了后面的递归过程就没办法考虑了！！

打家劫舍Ⅲ

  1. 给定一个二叉树，二叉树每个节点的值都是正整数，求二叉树中所有不相邻元素的最大和
  2. https://leetcode-cn.com/problems/house-robber-iii/
  3. 递归：要么是爷爷的钱+四个孙子的钱，要么是两个儿子的钱。
  4. 带记忆的递归：用HashMap存储！
  5. 无后效性+后序遍历：由于采用的是后序遍历，反而比数组的实现方式更简单，因为根本不需要dp数组，只需要一个含有两个元素的数组来消除后效性！！
  6. 我最初觉得这道题相比于前两道题目的最大难点在于不知道如何遍历，看完题解之后才发现自己的想法有多蠢，因为二叉树自有二叉树的遍历方式，后序遍历！
  7. 这道题目最大的难点其实和前两道题一样的，关键还是在于用dp的第二维消除后效性！dp[root][0]表示root不偷，dp[root][1]表示root偷。