代码随想录算法训练营第48天 | 198.打家劫舍, 213.打家劫舍II, 337.打家劫舍III

198.打家劫舍

代码随想录链接

题目

LeetCode-198.打家劫舍

思路分析

有一排屋子, 相邻两间房屋被闯入时会触发报警, 每个屋子都有一定数额的现金, 求能偷到的最高金额.

当前房屋偷和不偷取决与前一个房屋和前两个房屋是否被偷了, 就能形成一种递推关系.

动态规划五部曲:

• 确定dp数组及下标的含义

  \(dp[j]\)代表\([0, j]\)内的房屋, 最多可以偷\(dp[j]\)的金额.

• 确定递推公式

  到当前位置能偷多少可以从前两个位置的状态计算而来, 分别是偷前两个位置和当前位置, 或者是偷前一个位置, 故有:

  \[dp[j] = max(dp[j - 2] + nums[i], dp[j - 1]\]

• dp数组的初始化

  dp[0] = nums[0], dp[1] = max(nums[0], nums[1])

• 遍历顺序

  由公式: \[dp[j] = max(dp[j - 2] + nums[i], dp[j - 1]\] 可知遍历顺序一定是从前向后依次遍历.

• 举例推导

题解

class Solution {
public:
    int rob(vector<int>& nums) {
        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];
    }
};

213.打家劫舍II

代码随想录链接

题目

LeetCode-213.打家劫舍II

在第一题的基础上, 将房子首尾也连在一起, 即若首尾房子同时被入侵, 也会产生警报.

思路分析

可以将这个问题分解成两个子情况, 分别是不考虑首和不考虑尾, 并分别求出两个结果, 再取最大值.

题解

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

    int robRange(vector<int> &nums, int start, int end) { // 第一题的逻辑
        if (end == start)
            return nums[end];
        vector<int> dp(end - start + 1);
        dp[0] = nums[start];
        dp[1] = max(nums[start], nums[start + 1]);
        for (int i = start + 2; i <= end; i++)
            dp[i - start] = max(dp[i - start - 2] + nums[i], dp[i - start - 1]);
        return dp[end - start];
    }
};

337.打家劫舍III

代码随想录链接

题目

LeetCode-337.打家劫舍III

现在房屋以二叉树的形式进行排列, 直接相连的节点不能同时被入侵, 求最多能偷到的金额.

思路分析

上面两种情况都是后面的状态由前面决定, 而在二叉树中, 一个节点的状态应该由其子节点的状态决定, 所以应该用后序遍历来解决.

• 确定递归函数的参数和返回值

  需要知道偷与不偷这节点能获得的金额, 所以每个节点的向上返回值都应该包含两个值.

• 确定终止条件

  遇到空节点时, 直接返回{0, 0}

• 确定遍历顺序

  如上面分析, 一定是后序遍历

• 单层递归的逻辑

  先递归计算左右孩子偷与不偷分别能得到的金额, 再向上返回自己偷与不偷能获得的最大金额.

  vector<int> left = robTree(cur -> left);
  vector<int> right = robTree(cur -> right);
  int valDoCur = cur -> val + left[0] + right[0];
  int valNoCur = max(left[0], left[1]) + max(right[0], right[1]);
  return vector<int>{valNoCur, valDoCur};

题解

class Solution {
public:
    int rob(TreeNode* root) {
        vector<int> res = robTree(root);
        return max(res[0], res[1]);
    }

    vector<int> robTree(TreeNode *cur) {
        if (!cur)
            return vector<int> {0, 0};
        vector<int> left = robTree(cur -> left);
        vector<int> right = robTree(cur -> right);
        int valDoCur = cur -> val + left[0] + right[0];
        int valNoCur = max(left[0], left[1]) + max(right[0], right[1]);
        return vector<int>{valNoCur, valDoCur};
    }
};