C++刷题笔记(39)——打家劫舍、leetcode198、213、337

题目1：198.打家劫舍

1.确定dp数组以及下标的含义
要计算的是能偷窃到的最高金额，那么dp数组肯定就是最高金额，i则表示房屋的下标。

dp[i]：从下标[0,i]的房屋内最多可以偷窃的金额为dp[i]

2.确定状态转移方程
其实就算怎么偷才能得到最高金额
假设有i(i>2)间房，
如果偷窃第 i 间房屋，那么就不能偷窃第 k−1 间房屋，偷窃总金额为前 k−2 间房屋的最高总金额与第 k 间房屋的金额之和，即dp[i]=dp[i-2]+nums[i]；
如果不偷窃第 i 间房屋，偷窃第 i-1 间房，偷窃总金额为前 i−1 间房屋的最高总金额，即dp[i]=dp[i-1]。

那肯定找钱多的偷，那么dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])

3.dp数组初始化
dp[0]=nums[0]，即有一间房就偷一间房
dp[1]=max(nums[0],nums[1])，即有两间房就偷最有钱那间房

4.确定遍历顺序
dp[i] 是根据dp[i - 2] 和 dp[i - 1] 推导出来的，那么一定是从前到后遍历

5.举例推导do数组

class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.size() == 0) return 0;        //数组为空，偷不了
        if (nums.size() == 1) return nums[0];  //只有一间房，就偷它！
        vector<int> dp(nums.size());
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);
        for (int i = 2; i < nums.size(); i++) {
            dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[nums.size() - 1];
    }
};

官方还给了滚动数组的方法去优化

题目2：213.打家劫舍Ⅱ

和198相比这道题中的房屋成环了，因此第一件房屋和最后一间房屋不能同时偷盗了

假设有i间房(i>2)，
如果不偷第 i 间房，那么偷窃房屋的下标为[0,i-1]；
如果不偷第一间房，那么偷窃房屋的下标为[1,i];
确定偷窃房屋的下标之后，找能偷盗的最大金额就和198题是一样的了

class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        if (nums.size() == 1) return nums[0];
        int result1 = robRange(nums, 0, nums.size() - 2);   //不偷第 1 间房
        int result2 = robRange(nums, 1, nums.size() - 1);   //不偷第 i 间房
        return max(result1, result2);
    }
    int robRange(vector<int>& nums, int start, int end) {   //这里和198题的逻辑一样
        if (end == start) return nums[start];               //测试用例中有个[0,0]
        vector<int> dp(nums.size());
        dp[start] = nums[start];                            //初始化dp[0]
        dp[start + 1] = max(nums[start], nums[start + 1]);  //初始化dp[1]
        for (int i = start + 2; i <= end; i++) {
            dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[end];
    }
};

评论区大佬的题解也非常好，用两个dp数组去计算两种不同的情况：

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) return nums[0];       //只有一间房间，返回nums[0]
        vector<int>f(n + 1), g(n + 1);    //用两个dp数组应对两种不同的情况
        f[1] = nums[0], g[2] = nums[1];   //初始化
        for (int i = 2; i <= n - 1; i++)  f[i] = max(f[i - 1], f[i - 2] + nums[i - 1]); //区间[1,n-1]最大值
        for (int i = 3; i <= n; i++)      g[i] = max(g[i - 1], g[i - 2] + nums[i - 1]); //区间[2,n]最大值
        return max(f[n - 1], g[n]);
    }
};

题目3：337.打家劫舍Ⅲ

树形dp的入门题目
这里要先清楚怎么偷：
根据当前结点偷或者不偷，
如果当前结点不偷，左右子结点偷或者不偷都行，选最大者；
如果当前结点偷，左右子结点均不能偷。

class Solution {
public:
    vector<int> dfs(TreeNode* cur) {
        if (cur == nullptr) return { 0, 0 };                      //空节点返回，后续遍历
        vector<int> left = dfs(cur->left);                        //递归左节点，得到左节点偷与不偷的金钱
        vector<int> right = dfs(cur->right);                      //递归右节点，得到右节点偷与不偷的金钱

        vector<int> dp(2, 0);  //dp[0]为记录不偷该节点所得到的的最大金钱，dp[1]记录偷该节点所得到的的最大金钱
        dp[0] = max(left[0], left[1]) + max(right[0], right[1]);  // 当前结点不偷，那么就偷左右孩子大的
        dp[1] = cur->val + left[0] + right[0];                    // 当前结点偷，那么左右孩子就不能偷了
        return dp;
    }
    int rob(TreeNode* root) {
        vector<int> result = dfs(root);
        return max(result[0], result[1]);
    }
};

这里感觉用递归二叉树的思想更多一点