🦹‍♂️ 打家劫舍

📝 题目描述

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

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

📋 代码模版

java

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

    }
}

typescript

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

💡 提示

1. $1\le nums.length\le 100$
2. $0\le nums[i]\le 400$

🚀 示例

🖊️ 题解

记忆化搜索

​ 假设房屋从序号0开始排列，且n为nums.length - 1。

​ 我们可以先考虑最简单的情况。如果只有一间房屋（n == 0），则能够偷窃到的最高金额为该房屋中的现金金额。如果只有两间房屋（n == 1），由于两间房屋相龄，不能同时偷窃，则能够偷窃到的最高金额为这两间房屋中现金金额的较大值。

​ 如果房屋数量大于两间（n >= 2），那么小偷至第n间房屋能够偷窃到的最高金额计算可以分为以下两种情况。

1. 偷窃第n间房屋，那就不能偷窃第n - 1间房屋，偷窃最高金额为至第n - 2间房屋能够偷窃到的最高金额与第n间房屋内的现金金额之和。

2. 不偷窃第n间房屋，偷窃最高金额为至第n - 1间房屋能够偷窃到的最高金额。

​ 在以上两种情况中，选择偷窃最高金额较大的值，即为小偷至第n间房屋能够偷窃到的最高金额。

​ 在上述过程中，原问题被拆分为两个子问题。通过仔细观察这两个子问题，我们发现它们与原问题相似，只是规模更小，并且当子问题的答案不明确时，我们仍然可以将其进一步分解为更小的子问题。

​ 因此，该题可以使用深度优先搜索dfs来解决。我们定义 $dfs(i)$ 为⭐️至 第 $i$ 间房屋能够偷窃的最高金额⭐️，其中$0\le i\le n$。递归公式为 $dfs(i)=max(dfs(i-1),dfs(i-2)+nums[i])$，递归边界为$dfs(0)=nums[0],dfs(1)=max(nums[0],nums[1])$。

​ 综上所述，我们很容易写出以下代码。

java

class Solution {
    public int rob(int[] nums) {
        int n = nums.length - 1;
        return dfs(n, nums);
    }

    private int dfs(int i, int[] nums) {
        if (i == 0) {
            return nums[0];
        }
        if (i == 1) {
            return Math.max(nums[1], nums[0]);
        }
        return Math.max(dfs(i - 1, nums), dfs(i - 2, nums) + nums[i]);
    }
}

typescript

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

​ 😭但经过实践，当nums.length增大到一定阈值时，以上代码的提交大概率会因为超时而无法通过。

​ 那么，导致以上代码运行效率低下的原因是什么呢？接下来，让我们来分析一下它的时间复杂度。假设n = 5，可以画出以下递归树。

​ 递归树为一颗二叉树。其中，每个节点都代表一个子问题的计算，节点总数为指数级别。因此，我们可以得出结论：随着n的增大，由于重复计算不断增加，子问题的个数也随之呈指数级增长。基于此，这个算法的时间复杂度为 $O(2^n)$。

​ ⭐以上所述为多路递归的典型问题，即重复计算。为了应对这个问题，经典的解决方法是创建一个「备忘录」，在计算每个子问题之前先查找备忘录。如果备忘录中没有记录计算结果，就进行计算并将结果记录在备忘录中；反之，则直接获取记录的值并返回。

tip: 多路递归是指递归函数体中多次调用了自身。

​ 这种带备忘录的递归算法通常也被称为记忆化搜索，对应本题的算法代码如下。

java

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

    public int rob(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 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);
}

::

​ 记忆化搜索是一种典型的空间换时间的思想，它是在一颗存在大量冗余的递归树上通过「剪枝」，保证了每个相同的节点只计算一次。因此，该算法的时间复杂度为 $O(n)$，空间复杂度为 $O(n)$​。

动态规划

​ 根据以上dfs的解法，我们可以很轻松地将其翻译成动态规划dp解法，具体步骤如下。

1. 状态定义：设 $dp$ 为一维数组，其中 $dp[i]$ 表示⭐️至 第 $i$ 间房屋能够偷窃的最高金额⭐️。设$n=nums.length-1$，$0\le i\le n$。
2. 初始状态：根据边界条件，初始化 $dp$ 数组的前两项，即$dp[0]=nums[0],dp[1]=max(nums[0],nums[1])$。
3. 状态转移方程：$dp[i]=max(dp[i-1],dp[i-2]+nums[i])$，其中 $2\le i\le n$。
4. 返回值：$dp[n]$，即至第 $n$​ 间房屋能够偷窃的最高金额

java

java

class Solution {
    public int rob(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;
    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];
}

​ 以上算法需要一个很长的DP table（ $dp$ 数组）来存储所有的状态，但我们仔细观察状态转移方程$dp[i]=max(dp[i-1],dp[i-2]+nums[i])$，可以发现当前状态的计算只依赖于前两个状态。因此我们可以通过「滚动数组」的思想，利用若干变量替代 $dp$ 数组，在保持算法的时间复杂度不变的前提下，将空间复杂度从 $O(n)$ 优化至 $O(1)$。

​ 这种技巧通常也被称为状态压缩，对应本题的算法代码如下。

java

class Solution {
    public int rob(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;
    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)$ 。