198. 打家劫舍

写在前面

本专栏专注于分析与讲解【面试经典150】算法，两到三天更新一篇文章，欢迎催更……

专栏内容以分析题目为主，并附带一些对于本题涉及到的数据结构等内容进行回顾与总结，文章结构大致如下，部分内容会有增删：

• Tag：介绍本题牵涉到的知识点、数据结构；
• 题目来源：贴上题目的链接，方便大家查找题目并完成练习；
• 题目解读：复述题目（确保自己真的理解题目意思），并强调一些题目重点信息；
• 解题思路：介绍一些解题思路，每种解题思路包括思路讲解、实现代码以及复杂度分析；
• 知识回忆：针对今天介绍的题目中的重点内容、数据结构进行回顾总结。

---

Tag

【动态规划】【数组】【2023-09-16】

---

题目来源

198. 打家劫舍

---

题目解读

你是一个专业的小偷，现在要偷一排屋子，但是你不能偷相邻的两间屋子，求出你可以偷盗的最大价值。

---

解题思路

方法一：动态规划

状态

dp[i] 表示偷 nums[0...i] 屋子可以获得的最大值。

base case

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

状态转移

i>=2 时，dp[i] 可以从两个位置转移过来：

• 偷了 i 位置，那么上一次只能偷 i-2 位置的；
• 没有偷 i 位置，那么上一次可以偷 i-1 位置的；

最后的状态转移关系为：
$$dp[i]=max(dp[i-2]+nums[i],dp[i-1]);$$

最后返回

最后返回 dp[n-1]，即表示偷 nums[0...n-1] 可以获得最大金额（n 是 nums 数组的长度）。

实现代码

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

        for (int i = 2; i < n; ++i) {
            dp[i] = max(dp[i-2] + nums[i], dp[i-1]);
        }
        return dp[n-1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

复杂度分析

时间复杂度：$O(n)$，$n$ 数组 nums 的长度。

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

优化-状态压缩

通过观察状态转移式子，可以发现本次偷盗的最大价值和上次以及上上次偷盗的最大价值有关，因此可以用有限个变量来记录这两个参数，从而可以将空间复杂度降到 $O(1)$。

实现代码

class Solution {
public:
    int rob(vector<int>& nums) {
        int prev = 0, curr = 0;
        for (int num : nums) {
            int tmp = max(prev + num, curr);
            prev = curr;
            curr = tmp;
        }
        return curr;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

复杂度分析

时间复杂度：$O(n)$，$n$ 数组 nums 的长度。

空间复杂度：$O(1)$。

写在最后

如果文章内容有任何错误或者您对文章有任何疑问，欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度方法，欢迎评论区交流。

最后，感谢您的阅读，如果感到有所收获的话可以给博主点一个 👍 哦。