LeetCode 第198题：打家劫舍

题目描述

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

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

难度

中等

题目链接

点击在LeetCode中查看题目

示例

示例 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 <= nums.length <= 100
• 0 <= nums[i] <= 400

解题思路

方法一：动态规划

这是一个典型的动态规划问题，我们可以使用动态规划来解决。

关键点：

1. 定义状态：dp[i]表示偷窃前i个房屋能获得的最大金额
2. 状态转移方程：dp[i] = max(dp[i-1], dp[i-2] + nums[i])
3. 初始状态：dp[0] = nums[0], dp[1] = max(nums[0], nums[1])

时间复杂度：O(n)，其中n是房屋数量 空间复杂度：O(n)，需要存储dp数组

方法二：动态规划（空间优化）

我们可以优化空间复杂度，因为每个状态只依赖于前两个状态。

关键点：

1. 使用两个变量prev和curr来存储前两个状态
2. 每次更新时，prev = curr, curr = max(curr, prev + nums[i])
3. 最终返回curr

时间复杂度：O(n)，其中n是房屋数量 空间复杂度：O(1)，只需要常数额外空间

方法三：递归（记忆化搜索）

使用递归方法，配合记忆化搜索来避免重复计算。

关键点：

1. 定义递归函数rob(i)表示偷窃前i个房屋能获得的最大金额
2. 使用memo数组存储已计算的结果
3. 递归终止条件：i < 0时返回0

时间复杂度：O(n)，其中n是房屋数量 空间复杂度：O(n)，需要存储memo数组

代码实现

C# 实现

方法一：动态规划

public class Solution {
    public int Rob(int[] nums) {
        if (nums == null || nums.Length == 0) return 0;
        if (nums.Length == 1) return nums[0];
        
        int[] dp = new int[nums.Length];
        dp[0] = nums[0];
        dp[1] = Math.Max(nums[0], nums[1]);
        
        for (int i = 2; i < nums.Length; i++) {
            dp[i] = Math.Max(dp[i-1], dp[i-2] + nums[i]);
        }
        
        return dp[nums.Length - 1];
    }
}

方法二：动态规划（空间优化）

public class Solution {
    public int Rob(int[] nums) {
        if (nums == null || nums.Length == 0) return 0;
        if (nums.Length == 1) return nums[0];
        
        int prev = nums[0];
        int curr = Math.Max(nums[0], nums[1]);
        
        for (int i = 2; i < nums.Length; i++) {
            int temp = curr;
            curr = Math.Max(curr, prev + nums[i]);
            prev = temp;
        }
        
        return curr;
    }
}

方法三：递归（记忆化搜索）

public class Solution {
    private int[] memo;
    
    public int Rob(int[] nums) {
        if (nums == null || nums.Length == 0) return 0;
        
        memo = new int[nums.Length];
        Array.Fill(memo, -1);
        
        return RobHelper(nums, nums.Length - 1);
    }
    
    private int RobHelper(int[] nums, int i) {
        if (i < 0) return 0;
        if (memo[i] >= 0) return memo[i];
        
        memo[i] = Math.Max(
            RobHelper(nums, i - 1),
            RobHelper(nums, i - 2) + nums[i]
        );
        
        return memo[i];
    }
}

Python 实现

方法一：动态规划

class Solution:
    def rob(self, nums: List[int]) -> int:
        if not nums:
            return 0
        if len(nums) == 1:
            return nums[0]
            
        dp = [0] * len(nums)
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])
        
        for i in range(2, len(nums)):
            dp[i] = max(dp[i-1], dp[i-2] + nums[i])
            
        return dp[-1]

方法二：动态规划（空间优化）

class Solution:
    def rob(self, nums: List[int]) -> int:
        if not nums:
            return 0
        if len(nums) == 1:
            return nums[0]
            
        prev = nums[0]
        curr = max(nums[0], nums[1])
        
        for i in range(2, len(nums)):
            prev, curr = curr, max(curr, prev + nums[i])
            
        return curr

方法三：递归（记忆化搜索）

class Solution:
    def rob(self, nums: List[int]) -> int:
        if not nums:
            return 0
            
        memo = [-1] * len(nums)
        
        def rob_helper(i: int) -> int:
            if i < 0:
                return 0
            if memo[i] >= 0:
                return memo[i]
                
            memo[i] = max(
                rob_helper(i - 1),
                rob_helper(i - 2) + nums[i]
            )
            
            return memo[i]
            
        return rob_helper(len(nums) - 1)

C++ 实现

方法一：动态规划

class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.empty()) return 0;
        if (nums.size() == 1) return nums[0];
        
        vector<int> dp(nums.size());
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);
        
        for (int i = 2; i < nums.size(); i++) {
            dp[i] = max(dp[i-1], dp[i-2] + nums[i]);
        }
        
        return dp.back();
    }
};

方法二：动态规划（空间优化）

class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.empty()) return 0;
        if (nums.size() == 1) return nums[0];
        
        int prev = nums[0];
        int curr = max(nums[0], nums[1]);
        
        for (int i = 2; i < nums.size(); i++) {
            int temp = curr;
            curr = max(curr, prev + nums[i]);
            prev = temp;
        }
        
        return curr;
    }
};

方法三：递归（记忆化搜索）

class Solution {
private:
    vector<int> memo;
    
    int robHelper(vector<int>& nums, int i) {
        if (i < 0) return 0;
        if (memo[i] >= 0) return memo[i];
        
        memo[i] = max(
            robHelper(nums, i - 1),
            robHelper(nums, i - 2) + nums[i]
        );
        
        return memo[i];
    }
    
public:
    int rob(vector<int>& nums) {
        if (nums.empty()) return 0;
        
        memo.assign(nums.size(), -1);
        return robHelper(nums, nums.size() - 1);
    }
};

性能分析

各语言实现的性能对比：

实现语言	方法	执行用时	内存消耗	特点
C#	方法一	88 ms	24.8 MB	动态规划，直观高效
C#	方法二	84 ms	24.6 MB	空间优化，性能更好
C#	方法三	92 ms	25.1 MB	递归方式，代码清晰
Python	方法一	40 ms	14.9 MB	动态规划，实现简单
Python	方法二	36 ms	14.8 MB	空间优化，性能更好
Python	方法三	44 ms	15.1 MB	递归方式，易于理解
C++	方法一	4 ms	7.8 MB	动态规划，性能优秀
C++	方法二	0 ms	7.6 MB	空间优化，性能最优
C++	方法三	8 ms	8.1 MB	递归方式，代码优雅

补充说明

代码亮点

1. 方法一使用动态规划，实现简单直观
2. 方法二优化空间复杂度，性能更好
3. 方法三使用递归，代码结构清晰

动态规划解释

• 状态定义：dp[i]表示偷窃前i个房屋能获得的最大金额
• 状态转移：dp[i] = max(dp[i-1], dp[i-2] + nums[i])
• 初始状态：dp[0] = nums[0], dp[1] = max(nums[0], nums[1])

常见错误

1. 没有处理空数组和单元素数组的情况
2. 状态转移方程写错，导致结果错误
3. 递归方法中没有使用记忆化，导致超时
4. 空间优化方法中变量更新顺序错误

相关题目

• 197. 上升的温度
• 199. 二叉树的右视图
• 200. 岛屿数量