题解 | 打家劫舍(二)

1、解题思路

1. 问题分解：由于第一个和最后一个房间相邻，可以将问题分解为两种情况： 不偷最后一个房间（即只考虑前 n-1 个房间）。不偷第一个房间（即只考虑后 n-1 个房间）。两种情况的最大值即为最终答案。
2. 动态规划：对于非环形问题，使用动态规划： dp[i] = max(dp[i-1], dp[i-2] + nums[i])。对于环形问题，分别计算两种情况的最大值。
3. 空间优化：使用两个变量 prev1 和 prev2 来存储前两个状态，优化空间复杂度。

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];
        }
        if (n == 2) {
            return max(nums[0], nums[1]);
        }
        return max(robRange(nums, 0, n - 2), robRange(nums, 1, n - 1));
    }

    int robRange(vector<int>& nums, int start, int end) {
        int prev2 = 0, prev1 = 0;
        for (int i = start; i <= end; ++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];
        if (n == 2) return Math.max(nums[0], nums[1]);
        return Math.max(robRange(nums, 0, n - 2), robRange(nums, 1, n - 1));
    }

    private int robRange(int[] nums, int start, int end) {
        int prev2 = 0, prev1 = 0;
        for (int i = start; i <= end; 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]
        if n == 2:
            return max(nums[0], nums[1])
        return max(self.robRange(nums, 0, n - 2), self.robRange(nums, 1, n - 1))
    
    def robRange(self, nums: List[int], start: int, end: int) -> int:
        prev2, prev1 = 0, 0
        for i in range(start, end + 1):
            curr = max(prev1, prev2 + nums[i])
            prev2, prev1 = prev1, curr
        return prev1

3、复杂度分析

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