LC 213. 打家劫舍 II

题目描述

这是 LeetCode 上的 213. 打家劫舍 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 。

示例 3：

1
2
3

输入：nums = [0]

输出：0

提示：

$1 <= nums.length <= 100$
$0 <= nums[i] <= 1000$

动态规划

在 198. 打家劫舍中，并没有「第一间」和「最后一间」不能同时选择的限制，因此我们从头到尾做一遍 DP 即可。

在 198. 打家劫舍中，我们可以将状态定义为两维：

$f[i][j]$ 代表考虑前 $i$ 个房间，当前 $i$ 房间的现在状态为 $j$ 的最大价值。

$f[i][0]$ 代表考虑前 $i$ 个房间，并且「不选」第 $i$ 个房间的最大价值。由于已经明确了第 $i$ 个房间不选，因此 $f[i][0]$ 可以直接由 $max(f[i - 1][0], f[i - 1][1])$ 转移而来。
$f[i][1]$ 代表考虑前 $i$ 个房间，并且「选」第 $i$ 个房间的最大价值。由于已经明确了第 $i$ 个房间被选，因此 $f[i][1]$ 直接由 $f[i - 1][0] + nums[i]$ 转移过来。

到这里，你已经解决了 198. 打家劫舍了。

对于本题，由于只是增加了「第一间」和「最后一间」不能同时选择的限制。

通常，对于一些明显不是「增加维度」的新限制条件，我们应当考虑直接将其拎出讨论，而不是多增加一维进行状态记录。

我们可以把「第一间」&「最后一间」单独拎出来讨论：

明确「不选」第一间：
1. 初始化 $f[0][0]$ 和 $f[0][1]$，均为 $0$。
2. 先从「第二间」开始递推到「倒数第二间」的最大价值。
3. 再处理「最后一间」的情况：由于明确了「不选第一间」，则最后的最大价值为 $max(f[n - 2][1], f[n - 2][0] + nums[n - 1])$。
允许「选」第一间：
1. 初始化 $f[0][0]$ 和 $f[0][1]$，分别为 $0$ 和 $nums[0]$。
2. 先从「第二间」开始递推到「倒数第二间」的最大价值。
3. 再处理「最后一间」的情况：由于明确了「选第一间」，则最后的最大价值为 $max(f[n - 2][0], f[n - 2][1])$。

走完两遍 DP 后，再从两种情况的最大价值中再取一个 $max$ 即是答案。

Java 代码：

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;
        if (n == 1) return nums[0];

        // 第一间「必然不选」的情况
        int[][] f = new int[n][2];
        for (int i = 1; i < n - 1; i++) {
            f[i][0] = Math.max(f[i - 1][0], f[i - 1][1]);
            f[i][1] = f[i - 1][0] + nums[i];
        }
        int a = Math.max(f[n - 2][1], f[n - 2][0] + nums[n - 1]);
        
        // 第一间「允许选」的情况
        f[0][0] = 0; f[0][1] = nums[0];
        for (int i = 1; i < n - 1; i++) {
            f[i][0] = Math.max(f[i - 1][0], f[i - 1][1]);
            f[i][1] = f[i - 1][0] + nums[i];
        }
        int b = Math.max(f[n - 2][0], f[n - 2][1]);
        
        return Math.max(a, b);
    }
}

C++ 代码：

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        if (n == 1) return nums[0];

        vector<vector<int>> f(n, vector<int>(2, 0));
        for (int i = 1; i < n - 1; i++) {
            f[i][0] = max(f[i - 1][0], f[i - 1][1]);
            f[i][1] = f[i - 1][0] + nums[i];
        }
        int a = max(f[n - 2][1], f[n - 2][0] + nums[n - 1]);

        f[0][0] = 0; f[0][1] = nums[0];
        for (int i = 1; i < n - 1; i++) {
            f[i][0] = max(f[i - 1][0], f[i - 1][1]);
            f[i][1] = f[i - 1][0] + nums[i];
        }
        int b = max(f[n - 2][0], f[n - 2][1]);

        return max(a, b);
    }
};

Python 代码：

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 0: return 0
        if n == 1: return nums[0]

        f = [[0, 0] for _ in range(n)]
        for i in range(1, n - 1):
            f[i][0] = max(f[i - 1][0], f[i - 1][1])
            f[i][1] = f[i - 1][0] + nums[i]
        a = max(f[n - 2][1], f[n - 2][0] + nums[n - 1])

        f[0][0] = 0; f[0][1] = nums[0]
        for i in range(1, n - 1):
            f[i][0] = max(f[i - 1][0], f[i - 1][1])
            f[i][1] = f[i - 1][0] + nums[i]
        b = max(f[n - 2][0], f[n - 2][1])

        return max(a, b)

TypeScript 代码：

function rob(nums: number[]): number {
    const n: number = nums.length;
    if (n === 0) return 0;
    if (n === 1) return nums[0];

    const f: number[][] = new Array(n).fill(0).map(() => [0, 0]);
    for (let i: number = 1; i < n - 1; i++) {
        f[i][0] = Math.max(f[i - 1][0], f[i - 1][1]);
        f[i][1] = f[i - 1][0] + nums[i];
    }
    let a: number = Math.max(f[n - 2][1], f[n - 2][0] + nums[n - 1]);

    f[0][0] = 0; f[0][1] = nums[0];
    for (let i: number = 1; i < n - 1; i++) {
        f[i][0] = Math.max(f[i - 1][0], f[i - 1][1]);
        f[i][1] = f[i - 1][0] + nums[i];
    }
    let b: number = Math.max(f[n - 2][0], f[n - 2][1]);

    return Math.max(a, b);  
};

时间复杂度：$O(n)$
空间复杂度：$O(n)$

空间优化

不难发现，我们状态转移最多依赖到前面的 1 行，因此可以通过很机械的「滚动数组」方式将空间修改到 $O(1)$。

Java 代码：

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;
        if (n == 1) return nums[0];

        // 第一间「必然不选」的情况
        int[][] f = new int[2][2];
        for (int i = 1; i < n - 1; i++) {
            f[i%2][0] = Math.max(f[(i - 1)%2][0], f[(i - 1)%2][1]);
            f[i%2][1] = f[(i - 1)%2][0] + nums[i];
        }
        int a = Math.max(f[(n - 2)%2][1], f[(n - 2)%2][0] + nums[n - 1]);
        
        // 第一间「允许选」的情况
        f[0][0] = 0; f[0][1] = nums[0];
        for (int i = 1; i < n - 1; i++) {
            f[i%2][0] = Math.max(f[(i - 1)%2][0], f[(i - 1)%2][1]);
            f[i%2][1] = f[(i - 1)%2][0] + nums[i];
        }
        int b = Math.max(f[(n - 2)%2][0], f[(n - 2)%2][1]);
        
        return Math.max(a, b);
    }
}

C++ 代码：

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        if (n == 1) return nums[0];

        vector<vector<int>> f(2, vector<int>(2, 0));
        for (int i = 1; i < n - 1; i++) {
            f[i % 2][0] = max(f[(i - 1) % 2][0], f[(i - 1) % 2][1]);
            f[i % 2][1] = f[(i - 1) % 2][0] + nums[i];
        }
        int a = max(f[(n - 2) % 2][1], f[(n - 2) % 2][0] + nums[n - 1]);
        
        f[0][0] = 0; f[0][1] = nums[0];
        for (int i = 1; i < n - 1; i++) {
            f[i % 2][0] = max(f[(i - 1) % 2][0], f[(i - 1) % 2][1]);
            f[i % 2][1] = f[(i - 1) % 2][0] + nums[i];
        }
        int b = max(f[(n - 2) % 2][0], f[(n - 2) % 2][1]);
        
        return max(a, b);
    }
};

Python 代码：

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 0: return 0
        if n == 1: return nums[0]

        f = [[0, 0] for _ in range(2)]
        for i in range(1, n - 1):
            f[i % 2][0] = max(f[(i - 1) % 2][0], f[(i - 1) % 2][1])
            f[i % 2][1] = f[(i - 1) % 2][0] + nums[i]
        a = max(f[(n - 2) % 2][1], f[(n - 2) % 2][0] + nums[n - 1])
        
        f[0][0] = 0; f[0][1] = nums[0]
        for i in range(1, n - 1):
            f[i % 2][0] = max(f[(i - 1) % 2][0], f[(i - 1) % 2][1])
            f[i % 2][1] = f[(i - 1) % 2][0] + nums[i]
        b = max(f[(n - 2) % 2][0], f[(n - 2) % 2][1])
        
        return max(a, b)

TypeScript 代码：

function rob(nums: number[]): number {
    const n: number = nums.length;
    if (n === 0) return 0;
    if (n === 1) return nums[0];

    const f: number[][] = [[0, 0], [0, 0]];
    for (let i: number = 1; i < n - 1; i++) {
        f[i % 2][0] = Math.max(f[(i - 1) % 2][0], f[(i - 1) % 2][1]);
        f[i % 2][1] = f[(i - 1) % 2][0] + nums[i];
    }
    let a: number = Math.max(f[(n - 2) % 2][1], f[(n - 2) % 2][0] + nums[n - 1]);
    
    f[0][0] = 0; f[0][1] = nums[0];
    for (let i: number = 1; i < n - 1; i++) {
        f[i % 2][0] = Math.max(f[(i - 1) % 2][0], f[(i - 1) % 2][1]);
        f[i % 2][1] = f[(i - 1) % 2][0] + nums[i];
    }
    let b: number = Math.max(f[(n - 2) % 2][0], f[(n - 2) % 2][1]);
    
    return Math.max(a, b);
};

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

最后

这是我们「刷穿 LeetCode」系列文章的第 No.213 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

线性 DP

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

LC 778. 水位上升的泳池中游泳上一篇

LC 208. 实现 Trie (前缀树) 下一篇