Leetcode.198 打家劫舍

题目链接

Leetcode.198 打家劫舍 mid

题目描述

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

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

示例 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 。

提示：

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

解法一：记忆化搜索

我们定义 $dfs(i)$ 为小偷 偷窃 前 $i$ 个房间能够偷取的最大金额。

• 偷第 $i$ 个房间，能够偷取的最大金额为 $dfs(i-2)+nums[i]$；
• 不偷第 $i$ 个房间，能够偷取的最大值为 $dfs(i-1)$；

我们取二者的最大值，即 d f s ( i ) = m a x { d f s ( i − 2 ) + n u m s [ i ] , d f s ( i − 1 ) } dfs(i) = max \{ dfs(i - 2) + nums[i] , dfs(i - 1) \} dfs(i)=max{dfs(i−2)+nums[i],dfs(i−1)}。

当 $i<0$ 时，$dfs(i)=0$,表示没有房间可以偷了。

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

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

C++代码：

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n,-1);

        function<int(int)> dfs = [&](int i) ->int{
            if(i < 0) return 0;
            if(f[i] != -1) return f[i];

            int ans = max(dfs(i - 1) , dfs(i - 2) + nums[i]);
            f[i] = ans;
            
            return ans;
        };

        return dfs(n - 1);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

解法二：动态规划

我们将 记忆化搜索 一比一的翻译成 递推，即动态规划。

• d f s ( i ) = m a x { d f s ( i − 2 ) + n u m s [ i ] , d f s ( i − 1 ) } dfs(i) = max \{ dfs(i - 2) + nums[i] , dfs(i - 1) \} dfs(i)=max{dfs(i−2)+nums[i],dfs(i−1)}
• f ( i ) = m a x { f ( i − 2 ) + n u m s [ i ] , f ( i − 1 ) } f(i) = max \{ f(i - 2) + nums[i] , f(i - 1)\} f(i)=max{f(i−2)+nums[i],f(i−1)}；

当 $i<2$ 时，$i-2<0$ 越界了，所以我们直接将其整体偏移两个单位，即最终的式子为：

f ( i + 2 ) = m a x { f ( i ) + n u m s [ i ] , f ( i + 1 ) } f(i + 2) = max \{ f(i) + nums[i] , f(i + 1)\} f(i+2)=max{f(i)+nums[i],f(i+1)}

最终返回的答案为 $f(n+1)$ 。

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

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

C++代码：

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n + 2,0);
        for(int i = 0;i < n;i++){
            f[i + 2] = max(f[i + 1],f[i] + nums[i]);
        }
        return f[n + 1];
    }
};
1
2
3
4
5
6
7
8
9
10
11

解法三：动态规划 + 变量

对于式子 :

f ( i + 2 ) = m a x { f ( i ) + n u m s [ i ] , f ( i + 1 ) } f(i + 2) = max \{ f(i) + nums[i] , f(i + 1)\} f(i+2)=max{f(i)+nums[i],f(i+1)}

我们发现 $f(i+2)$ 始终只与 $f(i)$ 和 $f(i+1)$ 有关，$f(i+1)$ 是 前一个状态，$f(i)$ 是 前前一个状态。

我们直接定义 $f1$ 为 前一个状态，即 $f(i+1)$ ；$f0$ 为 前前一个状态，即 $f(i)$。

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

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

C++代码：

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        int f0 = 0 , f1 = 0;

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