代码随想录day39dp7

198. 打家劫舍

题目链接
文章讲解

class Solution {
public:
    int rob(vector<int>& nums) {
        // 特判：如果只有一个房子，直接偷这个房子
        if(nums.size() <= 1) return nums[0];
        // 特判：如果只有两个房子，偷价值更高的那个
        if(nums.size() == 2) return max(nums[0], nums[1]);

        // 1. 确定 dp 数组及其含义
        //    dp[i] 表示前 i+1 个房子中能偷到的最大金额（下标从 0 开始）
        vector<int> dp(nums.size(), 0);

        // 3. 初始化 dp 数组
        dp[0] = nums[0];                      // 第一个房子只能偷它自己
        dp[1] = max(nums[0], nums[1]);        // 第二个房子只能选第一个或第二个中较大的一个

        // 4. 确定遍历顺序（从前向后递推）
        for(int i = 2; i < nums.size(); i++) {
            // 2. 确定递推公式：
            //    对于第 i 个房子，有两个选择：
            //    - 不偷：dp[i] = dp[i-1]
            //    - 偷：  dp[i] = dp[i-2] + nums[i]
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
        }

        // 5. 举例推导（例如 nums = [2,7,9,3,1]）：
        //    dp[0] = 2
        //    dp[1] = max(2,7) = 7
        //    dp[2] = max(7,2+9)=11
        //    dp[3] = max(11,7+3)=11
        //    dp[4] = max(11,11+1)=12

        return dp[nums.size() - 1];  // 返回能偷到的最大金额
    }
};

213.打家劫舍II

题目链接
文章讲解

class Solution {
public:
    int rob(vector<int>& nums) {
        // 特判：没有房子，偷不到任何金额
        if(nums.size() == 0) return 0;

        // 特判：只有一个房子，只能偷这个房子
        if(nums.size() == 1) return nums[0];

        // 特判：只有两个房子，偷价值较高的那个
        if(nums.size() == 2) return max(nums[0], nums[1]);

        // 环形数组不能同时偷第一个和最后一个房子，因此划分为两个区间分别求解
        // 1. 不偷第一个房子，即考虑 nums[1...n-1]
        // 2. 不偷最后一个房子，即考虑 nums[0...n-2]

        vector<int> l(nums.begin() + 1, nums.end());   // nums[1 ~ n-1]
        vector<int> r(nums.begin(), nums.end() - 1);   // nums[0 ~ n-2]

        // 1. 确定 dp 数组及其含义：
        //    dp[i] 表示在当前区间中偷到第 i 个房子为止的最大金额
        vector<int> dp(l.size(), 0);   // 对区间 [1, n-1] 求解
        vector<int> dp2(r.size(), 0);  // 对区间 [0, n-2] 求解

        // 3. 初始化：
        // 对于两个区间分别初始化前两个状态
        dp[0] = l[0];                            // 只能偷 l[0]
        dp[1] = max(l[0], l[1]);                 // 偷 l[0] 或 l[1] 中的最大值
        dp2[0] = r[0];                           // 只能偷 r[0]
        dp2[1] = max(r[0], r[1]);                // 偷 r[0] 或 r[1] 中的最大值

        // 4. 遍历顺序：
        // 从第 3 个房子（即下标 2）开始遍历
        if (l.size() >= 2) {
            for (int i = 2; i < l.size(); i++) {
                // 2. 状态转移方程：
                //    偷第 i 个房子：dp[i] = dp[i - 2] + l[i]
                //    不偷第 i 个房子：dp[i] = dp[i - 1]
                dp[i] = max(dp[i - 1], dp[i - 2] + l[i]);
            }
        }

        if (r.size() >= 2) {
            for (int i = 2; i < r.size(); i++) {
                dp2[i] = max(dp2[i - 1], dp2[i - 2] + r[i]);
            }
        }

        // 5. 返回两个区间的最大值：
        // 最终结果是两段中能偷到的最大金额
        return max(dp[l.size() - 1], dp2[r.size() - 1]);
    }
};

337.打家劫舍 III

题目链接
文章讲解

class Solution {
public:
    int rob(TreeNode* root) {
        vector<int> result = robTree(root);
        return max(result[0], result[1]);  // 返回不偷根节点和偷根节点中的最大值
    }

    // 返回长度为 2 的数组，[0]：不偷当前节点，[1]：偷当前节点
    vector<int> robTree(TreeNode* node) {
        if (node == nullptr) {
            return {0, 0};  // 空节点时，偷与不偷的价值都是 0
        }

        // 递归计算左子树和右子树的最大偷窃金额
        vector<int> left = robTree(node->left);
        vector<int> right = robTree(node->right);

        // 不偷当前节点，则可以选择偷左子节点或不偷左子节点，偷右子节点或不偷右子节点
        int notRob = max(left[0], left[1]) + max(right[0], right[1]);

        // 偷当前节点，则不能偷左子节点和右子节点
        int rob = node->val + left[0] + right[0];

        return {notRob, rob};  // 返回不偷当前节点和偷当前节点的最大价值
    }
};