跳到主要内容

打家劫舍题库

打家劫舍​

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例1:

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例2:

输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

方案A 动态规划​

思路:

  1. 状态定义: 用 dp[i] 表示前 i 间房屋能偷窃到的最高总金额
  2. 状态转移方程: 对于第 k (k>2) 间房屋，有两个选项：
    • 偷窃第 k 间房屋，那么就不能偷窃第 k-1 间房屋，偷窃总金额为前 k-2 间房屋的最高总金额与第 k 间房屋的金额之和。
    • 不偷窃第 k 间房屋，偷窃总金额为前 k-1 间房屋的最高总金额。
    • 在两个选项中选择偷窃总金额较大的选项
    • 可得状态转移方程: dp[i]=max(dp[i−2]+nums[i],dp[i−1])
  3. 初始状态:
    • dp[0]=nums[0] 只有一间房屋，则偷窃该房屋
    • dp[1]=max(nums[0],nums[1]) 只有两件房屋，选择其中金额较高的房屋进行偷窃
  4. 问题答案:
  5. 优化空间:

:::details 优化空间前

function rob(nums) {
    if(nums.length==1){
        return nums[0];
    }
    let dp=new Array(nums.length);
    dp[0]=nums[0];
    dp[1]=Math.max(nums[0],nums[1]);
    for(let i=2;i<nums.length;i++){
        dp[i]=Math.max(dp[i-2]+nums[i],dp[i-1]);
    }
    return dp[nums.length-1];
};

:::

性能分析:

  • 时间复杂度：O(n)，其中 n 是数组长度。只需要对数组遍历一次。
  • 空间复杂度：O(n)。

:::details 优化空间后

function rob(nums) {
    if(nums.length==1){
        return nums[0];
    }
    dp0=nums[0];
    dp1=Math.max(nums[0],nums[1]);
    for(let i=2;i<nums.length;i++){
        let temp=dp1;
        dp1=Math.max(dp0+nums[i],dp1);
        dp0=temp;
    }
    return dp1;
};

:::

性能分析:

  • 时间复杂度：O(n)，其中 n 是数组长度。只需要对数组遍历一次。
  • 空间复杂度：O(1)。使用滚动数组，可以只存储前两间房屋的最高总金额，而不需要存储整个数组的结果，因此空间复杂度是 O(1)。

打家劫舍 II​

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

示例1:

输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

示例2:

输入：nums = [1,2,3,1]
输出：4
解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
     偷窃到的最高金额 = 1 + 3 = 4 。

整体思路:这道题中的房屋是首尾相连的，第一间房屋和最后一间房屋相邻，因此第一间房屋和最后一间房屋不能在同一晚上偷窃。

方案A 动态规划​

思路:

  1. 状态定义: 用 dp[i] 表示在下标范围 [start,i] 内可以偷窃到的最高总金额
  2. 状态转移方程: 假设数组 nums 的长度为 n。如果不偷窃最后一间房屋，则偷窃房屋的下标范围是 [0,n−2]；如果不偷窃第一间房屋，则偷窃房屋的下标范围是 [1,n−1]。在确定偷窃房屋的下标范围是 [start,end] 时:
    • dp[i]=max(dp[i−2]+nums[i],dp[i−1])
  3. 初始状态: 假设偷窃房屋的下标范围是 [start,end]
    • dp[start]=nums[start] 只有一间房屋，则偷窃该房屋
    • dp[start+1]=max(nums[start],nums[start+1])
  4. 问题答案: 分别取 (start,end)=(0,n−2) 和 (start,end)=(1,n−1) 进行计算，取两个 dp[end] 中的最大值，即可得到最终结果。

:::details 点击查看代码

function robRange(nums,start,end){
    let dp0=nums[start];
    let dp1=Math.max(nums[start],nums[start+1]);
    for(let i=start+2;i<=end;i++){
        let temp=dp1;
        dp1=Math.max(dp0+nums[i],dp1);
        dp0=temp;
    }
    return dp1;
}
function rob(nums) {
    let len=nums.length;
    if(len==1){
        return nums[0];
    }else if(len==2){
        return Math.max(nums[0],nums[1]);
    }
    return Math.max(robRange(nums,0,len-2),robRange(nums,1,len-1));
};

:::

性能分析:

  • 时间复杂度：O(n)，其中 n 是数组长度。需要对数组遍历两次，计算可以偷窃到的最高总金额。
  • 空间复杂度：O(1)。