题解 | 打家劫舍(一)

1、解题思路

1. 动态规划： 定义 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])最终答案为 dp[n-1]。
2. 空间优化： 由于 dp[i] 仅依赖于 dp[i-1] 和 dp[i-2]，可以只用两个变量来存储前两个状态，将空间复杂度优化为 O(1)。

2、代码实现

C++

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型vector
     * @return int整型
     */
    int rob(vector<int>& nums) {
        // write code here
        int n = nums.size();
        if (n == 1) {
            return nums[0];
        }

        int prev2 = nums[0], prev1 = max(nums[0], nums[1]);
        for (int i = 2; i < n; ++i) {
            int cur = max(prev1, prev2 + nums[i]);
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }
};

Java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型一维数组
     * @return int整型
     */
    public int rob (int[] nums) {
        // write code here
        int n = nums.length;
        if (n == 1) return nums[0];
        int prev2 = nums[0], prev1 = Math.max(nums[0], nums[1]);
        for (int i = 2; i < n; i++) {
            int curr = Math.max(prev1, prev2 + nums[i]);
            prev2 = prev1;
            prev1 = curr;
        }
        return prev1;
    }
}

Python

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param nums int整型一维数组 
# @return int整型
#
class Solution:
    def rob(self , nums: List[int]) -> int:
        # write code here
        n = len(nums)
        if n == 1:
            return nums[0]
        prev2, prev1 = nums[0], max(nums[0], nums[1])
        for i in range(2, n):
            curr = max(prev1, prev2 + nums[i])
            prev2, prev1 = prev1, curr
        return prev1

3、复杂度分析

• 时间复杂度 O(n)
• 空间复杂度 O(1)