FatGod Blog
搜索 K

Appearance

🦹‍♂️ 打家劫舍 II ​

📝 题目描述 ​

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

​ 给定一个非负整数数组nums，其每个元素nums[i]代表单个房屋中存放的现金金额，请你计算出在不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。

环状排列的房屋

📋 代码模版 ​

java
class Solution {
    public int rob(int[] nums) {

    }
}
typescript
function rob(nums: number[]): number {
    
}

💡 提示 ​

  1. 1≤nums.length≤100
  2. 0≤nums[i]≤1000

🚀 示例 ​

示例

🖊️ 题解 ​

​ 本题是题目打家劫舍的进阶版，因此在解决这道题之前，强烈建议先处理题目打家劫舍。两者唯一的区别为：本题中房屋是环状排列的，即首尾连接，而题目打家劫舍中的房屋是单排排列的。

​ 本题中，房屋呈环状排列，且不能偷窃相龄的房屋。这意味着如果房屋数量只有一个或两个，其与题目打家劫舍无差别，但如果房屋数量超过两个，则增加了不能同时偷窃第一个房屋和最后一个房屋这一限制。此时，若偷窃了第一个房屋，则必然不会偷窃最后一个房屋，同样地，若偷窃了最后一个房屋，则也必然不会偷窃第一个房屋。

​ 综上所述，如果房屋数量超过两个，我们可以忽略掉首尾房屋中的其中任意一个。设n = nums.length - 1，有以下两种选项。

  1. 忽略第一个房屋，房屋从1至n单排排列。
  2. 忽略最后一个房屋，房屋从0至n - 1单排排列。

​ 这样一来，两种选项下的房屋排列就都可以被视作为单排排列，我们只需比较这两种选项下的偷窃最高金额，并选择较大值。而对于盗窃单排排列的房屋的最大金额这一问题，我们已经在题目打家劫舍中解决过，直接调用相应的方法即可。

记忆化搜索 ​

java
class Solution {
    private static final int NOT_CAL = -1;

    public int rob(int[] nums) {
        boolean isSingle = nums.length == 1;
        if (isSingle){
            return sequenceRob(nums);
        }
        return Math.max(
                sequenceRob(Arrays.copyOfRange(nums, 0, nums.length - 1)),
                sequenceRob(Arrays.copyOfRange(nums, 1, nums.length))
        );
    }

    private int sequenceRob(int[] nums) {
        int n = nums.length - 1;
        int[] memory = new int[n + 1];
        Arrays.fill(memory, NOT_CAL);
        return dfs(n, nums, memory);
    }

    private int dfs(int i, int[] nums, int[] memory) {
        if (i == 0) {
            return nums[0];
        }
        if (i == 1) {
            return Math.max(nums[1], nums[0]);
        }
        if (memory[i] != NOT_CAL) {
            return memory[i];
        }
        return memory[i] = Math.max(dfs(i - 1, nums, memory)
                , dfs(i - 2, nums, memory) + nums[i]);
    }
}
typescript
function rob(nums: number[]): number {
    const n = nums.length - 1;
    const isSingle = nums.length == 1;
    if (isSingle) {
        return sequenceRob(nums);
    }
    return Math.max(sequenceRob(nums.slice(0, n)), sequenceRob(nums.slice(1, n + 1)));
}

function sequenceRob(nums: number[]): number {
    const n = nums.length - 1;
    const memory: number[] = [];
    const dfs = (i: number): number => {
        if (i == 0) {
            return nums[0];
        }
        if (i == 1) {
            return Math.max(nums[0], nums[1]);
        }
        if (memory[i] !== undefined) {
            return memory[i];
        }
        return memory[i] = Math.max(dfs(i - 1), dfs(i - 2) + nums[i]);
    }
    return dfs(n);
}

动态规划 ​

普通版 ​

java
class Solution {
    public int rob(int[] nums) {
        boolean isSingle = nums.length == 1;
        if (isSingle) {
            return sequenceRob(nums);
        }
        return Math.max(
                sequenceRob(Arrays.copyOfRange(nums, 0, nums.length - 1)),
                sequenceRob(Arrays.copyOfRange(nums, 1, nums.length))
        );
    }

    private int sequenceRob(int[] nums) {
        int n = nums.length - 1;
        if (n == 0) {
            return nums[0];
        }
        int[] dp = new int[n + 1];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i <= n; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return dp[n];
    }
}
typescript
function rob(nums: number[]): number {
    const n = nums.length - 1;
    const isSingle = nums.length == 1;
    if (isSingle) {
        return sequenceRob(nums);
    }
    return Math.max(sequenceRob(nums.slice(0, n)), sequenceRob(nums.slice(1, n + 1)));
}

function sequenceRob(nums: number[]): number {
    const n = nums.length - 1;
    if (n == 0) {
        return nums[0];
    }
    const dp: number[] = [];
    dp[0] = nums[0];
    dp[1] = Math.max(nums[0], nums[1]);
    for (let i = 2; i <= n; i++) {
        dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
    }
    return dp[n];
}

状态压缩版 ​

java
class Solution {
    public int rob(int[] nums) {
        boolean isSingle = nums.length == 1;
        if (isSingle) {
            return sequenceRob(nums);
        }
        return Math.max(
                sequenceRob(Arrays.copyOfRange(nums, 0, nums.length - 1)),
                sequenceRob(Arrays.copyOfRange(nums, 1, nums.length))
        );
    }

    private int sequenceRob(int[] nums) {
        int n = nums.length - 1;
        if (n == 0) {
            return nums[0];
        }
        int pre = nums[0], cur = Math.max(nums[0], nums[1]);
        for (int i = 2; i <= n; i++) {
            int max = Math.max(cur, pre + nums[i]);
            pre = cur;
            cur = max;
        }
        return cur;
    }
}
typescript
function rob(nums: number[]): number {
    const n = nums.length - 1;
    const isSingle = nums.length == 1;
    if (isSingle) {
        return sequenceRob(nums);
    }
    return Math.max(sequenceRob(nums.slice(0, n)), sequenceRob(nums.slice(1, n + 1)));
}

function sequenceRob(nums: number[]): number {
    const n = nums.length - 1;
    if (n == 0) {
        return nums[0];
    }
    let pre = nums[0], cur = Math.max(nums[0], nums[1]);
    for (let i = 2; i <= n; i++) {
        const max = Math.max(cur, pre + nums[i]);
        pre = cur;
        cur = max;
    }
    return cur;
}

💭 复杂度分析 ​

​ 基于记忆化搜索的解决方案的复杂度分析如下。

  • 时间复杂度：O(n)。
  • 空间复杂度：O(n) 。

​ 基于动态规划的最优（状态压缩）解决方案的复杂度分析如下。

  • 时间复杂度：O(n)。
  • 空间复杂度：O(1) 。

上次更新于: