Medium

题目描述

你是一个专业的强盗，计划在一条街上抢劫房屋。每栋房子都藏有一定数量的钱，并由带有颜色代码的安全系统保护。

给你两个整数数组 nums 和 colors，长度均为 n，其中 nums[i] 是第 i 栋房子里的钱数，colors[i] 是该房子的颜色代码。

如果两栋相邻的房子有相同的颜色代码，你就不能同时抢劫它们。

返回你能抢劫的最大金额。

示例 1：

输入：nums = [1,4,3,5], colors = [1,1,2,2]
输出：9
解释：选择房子 i = 1（nums[1] = 4）和 i = 3（nums[3] = 5），因为它们不相邻。
因此，抢劫的总金额是 4 + 5 = 9。

示例 2：

输入：nums = [3,1,2,4], colors = [2,3,2,2]
输出：8
解释：选择房子 i = 0（nums[0] = 3）、i = 1（nums[1] = 1）和 i = 3（nums[3] = 4）。
这个选择是有效的，因为房子 i = 0 和 i = 1 有不同的颜色，房子 i = 3 与 i = 1 不相邻。
因此，抢劫的总金额是 3 + 1 + 4 = 8。

示例 3：

输入：nums = [10,1,3,9], colors = [1,1,1,2]
输出：22
解释：选择房子 i = 0（nums[0] = 10）、i = 2（nums[2] = 3）和 i = 3（nums[3] = 9）。
这个选择是有效的，因为房子 i = 0 和 i = 2 不相邻，房子 i = 2 和 i = 3 有不同的颜色。
因此，抢劫的总金额是 10 + 3 + 9 = 22。

约束条件：

  • 1 <= n == nums.length == colors.length <= 10^5
  • 1 <= nums[i], colors[i] <= 10^5

解题思路

这是一道动态规划题目，是经典打家劫舍问题的变种。核心思路是在原有的相邻约束基础上，增加了颜色约束。

思路分析：

定义 dp[i] 表示考虑前 i+1 栋房子（索引 0 到 i）能够抢劫的最大金额。对于每个位置 i，我们有两种选择：

  1. 不抢第 i 栋房子：dp[i] = dp[i-1]
  2. 抢第 i 栋房子：需要考虑约束条件

如果抢第 i 栋房子，有两种情况：

  • 如果 colors[i] != colors[i-1]（颜色不同），可以考虑抢相邻的前一栋：nums[i] + dp[i-1]
  • 总是可以考虑抢非相邻的前两栋：nums[i] + dp[i-2]（当 i >= 2 时）

关键观察：当相邻房子颜色不同时，相邻约束被解除，此时问题退化为普通的序列最大和问题。

状态转移方程：

  • 当 i == 0 时：dp[0] = nums[0]
  • 当 i == 1 时：dp[1] = max(nums[1], dp[0]) 如果颜色不同，否则 dp[1] = max(nums[1], nums[0])
  • 当 i >= 2 时：dp[i] = max(dp[i-1], nums[i] + max(dp[i-2], dp[i-1] if colors[i] != colors[i-1] else 0))

推荐解法： 动态规划，时间复杂度 O(n)，空间复杂度 O(1)（可优化为只使用两个变量）。

代码实现

class Solution {
public:
    long long rob(vector<int>& nums, vector<int>& colors) {
        int n = nums.size();
        if (n == 1) return nums[0];
        
        long long prev2 = nums[0];
        long long prev1 = (colors[0] != colors[1]) ? 
                         max((long long)nums[1], prev2 + nums[1]) : 
                         max((long long)nums[1], prev2);
        
        for (int i = 2; i < n; i++) {
            long long curr = max(prev1, (long long)nums[i] + prev2);
            if (colors[i] != colors[i-1]) {
                curr = max(curr, (long long)nums[i] + prev1);
            }
            prev2 = prev1;
            prev1 = curr;
        }
        
        return prev1;
    }
};

class Solution:
    def rob(self, nums: List[int], colors: List[int]) -> int:
        n = len(nums)
        if n == 1:
            return nums[0]
        
        prev2 = nums[0]
        prev1 = max(nums[1], prev2 + nums[1]) if colors[0] != colors[1] else max(nums[1], prev2)
        
        for i in range(2, n):
            curr = max(prev1, nums[i] + prev2)
            if colors[i] != colors[i-1]:
                curr = max(curr, nums[i] + prev1)
            prev2 = prev1
            prev1 = curr
        
        return prev1

public class Solution {
    public long Rob(int[] nums, int[] colors) {
        int n = nums.Length;
        if (n == 1) return nums[0];
        
        long prev2 = nums[0];
        long prev1 = (colors[0] != colors[1]) ? 
                     Math.Max(nums[1], prev2 + nums[1]) : 
                     Math.Max(nums[1], prev2);
        
        for (int i = 2; i < n; i++) {
            long curr = Math.Max(prev1, nums[i] + prev2);
            if (colors[i] != colors[i-1]) {
                curr = Math.Max(curr, nums[i] + prev1);
            }
            prev2 = prev1;
            prev1 = curr;
        }
        
        return prev1;
    }
}

var rob = function(nums, colors) {
    const n = nums.length;
    if (n === 0) return 0;
    if (n === 1) return nums[0];
    
    const dp = new Array(n).fill(0);
    dp[0] = nums[0];
    dp[1] = Math.max(nums[0], nums[1]);
    
    for (let i = 2; i < n; i++) {
        dp[i] = Math.max(dp[i-1], nums[i] + dp[i-2]);
        
        if (colors[i] === colors[i-1]) {
            dp[i] = Math.max(dp[i-1], nums[i] + (i >= 2 ? dp[i-2] : 0));
        } else {
            dp[i] = Math.max(dp[i-1], nums[i] + dp[i-1]);
        }
    }
    
    return dp[n-1];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)遍历一次数组，每个元素常数时间处理
空间复杂度O(1)只使用常数个变量存储状态

相关题目