三个打家劫舍

198. 打家劫舍

每个点选或不选，每个状态由上一个转移而来

class Solution {
public:
    int rob(vector<int>& nums) {
        int res = 0;
        int n = nums.size();
        vector<vector<int>> dp(n, vector<int>(2));
        dp[0][1] = nums[0];

        for (int i = 1; i < n; i ++)
        {
            dp[i][0] = max(dp[i-1][1], dp[i-1][0]);
            dp[i][1] = dp[i-1][0] + nums[i];
        }

        return max(dp[n-1][0], dp[n-1][1]);
    }
};

213. 打家劫舍 II

左右截掉一个点，两个取最大

class Solution {
public:
    int solve(vector<int>& nums)
    {
        int res = 0;
        int n = nums.size();
        vector<vector<int>> dp(n, vector<int>(2));
        dp[0][1] = nums[0];

        for (int i = 1; i < n; i ++)
        {
            dp[i][0] = max(dp[i-1][1], dp[i-1][0]);
            dp[i][1] = dp[i-1][0] + nums[i];
        }

        return max(dp[n-1][0], dp[n-1][1]);
    }

    int rob(vector<int>& nums) {
        if (nums.size() == 1) return nums[0];
        vector<int> nums1(nums.begin(), nums.end() - 1);
        vector<int> nums2(nums.begin() + 1, nums.end());
        return max(solve(nums1), solve(nums2));
    }
};

337. 打家劫舍 III

树形dp，向上返回当前所能达到的最大值。

class Solution {
public:
    unordered_map<TreeNode*, int> umap;  
    // 向上返回更大的, 选或不选
    int rob(TreeNode* root) {
        if (root == nullptr) return 0;
        if (root->left == nullptr && root->right == nullptr) return root->val;
        if (umap.count(root)) return umap[root];

        int val1 = root->val;
        if (root->left) val1 += rob(root->left->left) + rob(root->left->right);
        if (root->right) val1 += rob(root->right->left) + rob(root->right->right);

        int val2 = 0;
        val2 += rob(root->left) + rob(root->right);

        return umap[root] = max(val1, val2);
    }
};