打家劫舍V-LeetCode

3840. 打家劫舍 V - House Robber V

🎯 问题描述（来源于LeetCode）

描述：
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，每间房还有一个颜色代码。
与传统的打家劫舍不同，本题的限制为：相邻且颜色相同的房屋不能在同一晚上被偷。
即：如果两间相邻的房屋颜色不同，则可以同时偷窃；如果颜色相同，则不能同时偷窃。
给定两个数组 nums（金额）和 colors（颜色），返回不触发警报的情况下能偷窃到的最大金额。

说明：

• 相邻房屋之间只有颜色相同时才有额外限制。
• 数组长度 1 <= n <= 10^5。

示例：

• 示例 1：

输入: nums = [1,4,3,5], colors = [1,1,2,2]
输出: 9
解释: 偷第1间(4)和第3间(5)，不相邻，金额=9。

• 示例 2：

输入: nums = [3,1,2,4], colors = [2,3,2,2]
输出: 8
解释: 偷第0间(3)、第1间(1)、第3间(4)，相邻且颜色不同(3和1不同)允许，总金额=8。

💻 解题思路

思路：动态规划（按您的代码）

算法步骤

1. 获取房屋数量 n，创建 dp 数组，dp[i] 表示考虑前 i+1 间房屋（下标 0…i）能获得的最大金额。
2. 处理第一间房屋（i=0）：dp[0] = nums[0]。
3. 处理第二间房屋（i=1）：
   • 判断 colors[0] == colors[1]。
   • 若相同，则不能同时偷，取 max(dp[0], nums[1])。
   • 若不同，则可以同时偷，取 dp[0] + nums[1]。
4. 对于 i >= 2：
   • 判断 colors[i-1] == colors[i]。
   • 若不同，则当前房屋可以与前一个同时偷：dp[i] = dp[i-1] + nums[i]。
   • 若相同，则当前房屋不能与前一个同时偷，需要比较两种情况：偷当前房屋则加上 dp[i-2] + nums[i]，不偷则保持 dp[i-1]，取最大值。
5. 返回 dp[n-1]。

代码实现

from typing import List

class Solution:
    def rob(self, nums: List[int], colors: List[int]) -> int:
        n = len(nums)
        dp = [0] * n
        for i, color in enumerate(colors):
            if i == 0:
                dp[i] = nums[i]
                continue
            if i == 1:
                co = colors[i-1] == color
                if co:
                    dp[1] = max(dp[0], nums[1])
                else:
                    dp[1] = dp[0] + nums[1]
                continue
            co = colors[i-1] == color
            if not co:
                value = dp[i-1] + nums[i]
            else:
                value = max(dp[i-2] + nums[i], dp[i-1])
            dp[i] = value
        return dp[n-1]

📊 性能分析

• 时间复杂度：$O(n)$，一次遍历。
• 空间复杂度：$O(n)$，使用了 dp 数组。可优化到 $O(1)$（只保留前两个状态）。

思考

代码正确实现了题目要求的状态转移，逻辑清晰：分别处理了 i=0, i=1 和 i>=2 的情况，并根据相邻颜色是否相同来决定转移方程。
优点：直接对应问题定义，易于理解。
可优化点：可以使用滚动变量代替数组，降低空间复杂度至 $O(1)$。另外，对于 i=1 的情况，可以用统一的转移公式 dp[i] = max(dp[i-1], dp[i-2] + nums[i]) 并在颜色相同时禁止同时偷，但手动分支同样正确。