198. 打家劫舍">198. 打家劫舍
213. 打家劫舍 II">213. 打家劫舍 II
337. 打家劫舍 III">337. 打家劫舍 III
- 记忆化递归
- 动态规划
  - 用哈希表记录某个节点选不选的值
  - 用两个元素的数组记录抢不抢的状态

198. 打家劫舍

解题思路：
动态规划问题，和贪心类似，找到子问题，并且子问题会重复，将子问题保存
每到一个房子，都有抢和不抢两种选择
记dp[i]为到第i间房所能获得的最大利益，第i间房有抢或者不抢两种选择：

如果不抢的话，收益为dp[i-1]，这里第 i -1 间房间抢不抢都可以
如果抢的话，收益为 nums[i] + dp[n-2]。如果抢第i间房，那么必然不能考虑第i-1间房

所以此题目的状态转移方程为dp[i] = max (dp[i-1]) , nums[i] + dp[n-2])
初始化：dp[0]肯定是0了，dp[1]表示到第一间房，能获得最大收益，那必然是抢这一间房带来的，dp[1] = nums[0]

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        vector<int> dp(n + 1, 0);
        dp[1] = nums[0];
        for (int i = 2; i <= n; i++) {
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1]);
        }
        return dp[n];
    }
};

dp[i]的状态只与dp[i - 1]和dp[i - 2]有关，因此可优化空间复杂度：

class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.size() == 0)
            return 0;
        int n = nums.size();
        if (n == 1)
            return nums[0];
        int pre2 = 0, pre1 = 0, cur;
        for (int i = 0; i < n; i++) {
            cur = max(pre2 + nums[i], pre1);
            pre2 = pre1;
            pre1 = cur;
        }
        return cur;

    }
};

如果dp数组的下标代表nums的下标的话，那么初始化的条件要改变，初始化dp[0] = nums[0], dp[1] = max(dp[0], nums[1])

213. 打家劫舍 II

和打家劫舍1不同，这道题最后一间房和第一间房首尾相连，

如果只有一间房，偷了它可以得到最大金额
如果有两间房，偷金额最大的即可
如果房间大于两间要考虑首尾的问题，最后一间房和第一间房不能同时偷，所以要分情况讨论：
- 偷第一间房，那么不能偷最后一间房，那么用动态规划考虑的数组范围为第一间房到倒数第二间房，即 nums[0] ~ nums[n - 2]
- 不偷第一间房，那么考虑的数组范围变为第二间房到最后一间房，即 nums[1] ~ nums[n - 1] ```cpp class Solution { public: int rob(vector& nums) { int n = nums.size(); if (n == 0) return 0; if (n <= 2) return *max_element(nums.begin(), nums.end());
  
  //偷第一间房 int max_value; vector dp(n + 1, 0); dp[1] = nums[0];//i: 1 ~ n-1 for (int i = 2; i < n; ++i) {
```
   dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1]);
```
  } max_value = dp[n - 1];
  
  //不偷第一间房，最后一间房偷不偷都可以 fill(dp.begin(), dp.end(), 0); dp[2] = nums[1];//从第二间房开始考虑 for (int i = 3; i <= n; ++i) {
```
   dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1]);
```
  } max_value = max(max_value, dp[n]);
  
  return max_value; } };

空间复杂度优化
```cpp
class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        if (n <= 2) return *max_element(nums.begin(), nums.end());

        return max(rob_support(nums, 0, n - 1), rob_support(nums, 1, n));
    }

    int rob_support(vector<int> &nums, int left, int right) {
        int pre2 = 0, pre1 = 0;
        int cur;
        for (int i = left; i < right; ++i) { // 这种情况循环仅代表迭代次数
            cur = max(pre1, pre2 + nums[i]);
            pre2 = pre1;
            pre1 = cur;
        }
        return cur;
    }
};

337. 打家劫舍 III

树的问题需要考虑遍历顺序，因为需要递归函数的返回值来进行下一步计算，因此本题要后序遍历
暴力递归的话因为会重复计算某些值，所以会超时，记忆化递归（带备忘录的递归，动态规划）可以解决这个问题

记忆化递归

class Solution {
public:
    unordered_map<TreeNode* , int> umap; // 记录计算过的结果
    int rob(TreeNode* root) {
        if (root == NULL) return 0;
        if (root->left == NULL && root->right == NULL) return root->val;
        if (umap[root]) return umap[root]; // 如果umap里已经有记录则直接返回
        // 偷父节点
        int val1 = root->val;
        if (root->left) val1 += rob(root->left->left) + rob(root->left->right); // 跳过root->left
        if (root->right) val1 += rob(root->right->left) + rob(root->right->right); // 跳过root->right
        // 不偷父节点
        int val2 = rob(root->left) + rob(root->right); // 考虑root的左右孩子
        umap[root] = max(val1, val2); // umap记录一下结果
        return max(val1, val2);
    }
};

时间复杂度：O(n)
空间复杂度：O(logn) 算上递推系统栈的空间
动态规划

用哈希表记录某个节点选不选的值

f记录选，g记录不选
如果选当前节点，那么不能选左右孩子
如果不选当前节点，左右孩子可以选也可以不选
后序遍历，从叶子结点往上推

class Solution {
public:
    unordered_map<TreeNode*, int> f, g;
    void dfs(TreeNode* node) {
        if (node == nullptr) return;
        dfs(node->left);
        dfs(node->right);
        f[node] = node->val + g[node->left] + g[node->right]; // 选根结点
        g[node] = max(f[node->left], g[node->left]) + max(f[node->right], g[node->right]); // 不选根结点
    }
    int rob(TreeNode* root) {
        dfs(root);
        return max(f[root], g[root]);
    }
};

用两个元素的数组记录抢不抢的状态

每次递归的时候可以返回一个长度为2的数组，下标0代表不偷当前节点的最大收益，下标1代表偷当前节点的最大收益，那么这样就可以实现对某节点偷与不偷状态的记录

如果是偷当前节点，那么左右孩子就不能偷，val1 = cur->val + left[0] + right[0]; （如果对下标含义不理解就在回顾一下dp数组的含义）
如果不偷当前节点，那么左右孩子就可以偷，至于到底偷不偷一定是选一个最大的，所以：val2 = max(left[0], left[1]) + max(right[0], right[1]);
最后当前节点的状态就是{val2, val1}; 即：{不偷当前节点得到的最大金钱，偷当前节点得到的最大金钱}

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]);
return {val2, val1};

最后头结点就是取下标0 和下标1的最大值就是偷得的最大金钱。

class Solution {
public:
    vector<int> robTree(TreeNode* cur) {
        if (!cur) return {0, 0}; // 终止条件
        vector<int> left = robTree(cur->left);
        vector<int> right = robTree(cur->right);
        // 抢当前节点
        int val1 = cur->val + left[0] + right[0]; // 左右节点都不能抢
        // 不抢当前节点
        int val2 = max(left[0], left[1]) + max(right[0], right[1]);
        return {val2, val1};
    }
    int rob(TreeNode* root) {
        vector<int> res = robTree(root);
        return max(res[0], res[1]);
    }
};

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