2026-06-12：打家劫舍 V。用go言语，你当今要处置一个“相邻房屋不可同色同期偷”的求最大收益问题：
• 每间房屋还有一个神色代码 colors[i]。
• 法规是：要是两间房屋相邻（下标 i 和 i+1）且它们的神色代码换取，那么这两间不可同期被偷。
• 在随和上述收尾的前提下，选拔要偷的房屋，使得获取的总金额最大。
• 请输出在最优选拔下能得到的最大总金额。
1
1
输入： nums = [10，1，3，9]， colors = [1，1，1，2]。
输出： 22。
阐述：
选拔第 i = 0 间房屋（金额为 10）、第 i = 2 间房屋（金额为 3）和第 i = 3 间房屋（金额为 9）。
此选拔是正当的，因为第 i = 0 和 i = 2 间房屋不相邻，且第 i = 2 和 i = 3 间房屋神色不同。
因此，偷窃的总金额为 10 + 3 + 9 = 22。
题目来独力扣3840。
一、逐轮分步演算圆善经过（以示例nums=[10，1，3，9]、colors=[1，1，1，2]为例）
运行化阶段（i=0，第一间房屋）
房屋0：金额10，神色1
• 数组长度不为0，跳过领域复返0逻辑
• f1运行化为0：不偷0号房，收益0
• f2运行化为10：偷0号房，收益10
现时情状：f1=0（不偷0），f2=10（偷0）
第一轮轮回：i=1（第二间房屋，金额1，神色1）
博亚体育app2026世界杯中国官网下载对比相邻神色：colors[1]=1，colors[0]=1，相邻同色，触发同色分支逻辑。
法规：i和i-1同色，不可同期偷i和i-1，因此偷现时i的决策只可来自「不偷i-1的收益f1 + 现时房屋金额」，再和「不偷现时i，保留偷i-1的收益f2」取更大值看成money。
1. 候选1（偷1号房）：f1 + nums[1] = 0 + 1 = 1
2. 候选2（不偷1号房）：f2 = 10
3. 二者取大，money = max(1，10) = 10
4. 转动更新情状：
f1 = 旧f2 = 10（当今f1代表不偷1号房的最大收益）
f2 = money = 10（当今f2代表偷1号房的最大收益）
本轮收场情状：f1=10，f2=10
第二轮轮回：i=2（第三间房屋，金额3，神色1）
对比相邻神色：colors[2]=1，colors[1]=1，相邻同色，再次参加同色分支。
1. 候选1（偷2号房）：f1 + nums[2] = 10 + 3 = 13
2. 候选2（不偷2号房）：f2 = 10
3. 二者取大，money = max(13，10) = 13
4. 转动更新情状：
f1 = 旧f2 = 10（不偷2号房最大收益）
f2 = money = 13（偷2号房最大收益）
本轮收场情状：f1=10，f2=13
解读：此时偷2号房最优收益13，对应决策是不偷1号、偷0号+偷2号（10+3=13），和题目最优决策中间材干匹配。
第三轮轮回：i=3（第四间房屋，金额9，神色2）
对比相邻神色：colors[3]=2，colors[2]=1，相邻异色，凤凰彩票官网首页 - Welcome参加异色分支逻辑。
法规：i和i-1神色不同，无偷窃突破，不错同期偷i-1和i，因此偷现时i的收益 = 偷i-1的最大收益f2 + 现时房屋金额，径直赋值给money。
1. money = f2 + nums[3] = 13 + 9 = 22
2. 转动更新情状：
f1 = 旧f2 = 13（不偷3号房的最大收益）
f2 = money = 22（偷3号房的最大收益）
本轮收场情状：f1=13，f2=22
轮回收场，复返收尾
轮回遍历完总计4间房屋，最终f2存储遍历到终末一间房屋、偷终末一间时的全局最大收益，复返22，和题目输出一致。
二、通用算法圆善逻辑材干（脱离示例，通用处置随性n间房屋）
材干1：领域判断
要是房屋总和n=0，不存在可偷窃房屋，径直复返总收益0。
材干2：DP情状运行化（处置第0号首间房屋）
• f1：不偷第0间，收益固定为0；
• f2：偷第0间，收益就是第一间房屋金额nums[0]；
材干3：从第1间到终末一间，交替遍历每一间房屋i（轮回i=1 ~ n-1）
每一次轮回现实固定三步：
材干3.1 判断现时i和前一间i-1的神色关连
分支A：colors[i] != colors[i-1]（相邻异色）
相邻异色无偷窃突破，不错同期偷前一间和现时间。
现时房屋偷窃最优收益money = 偷前一间的最大收益f2 + 现时房屋金额nums[i]
分支B：colors[i] == colors[i-1]（相邻同色）
相邻同色不可两间齐偷，有两种选拔：
1. 不偷现时房屋：收益=偷前一间的收益f2；
2. 偷现时房屋：只可不偷前一间，收益=不偷前一间的收益f1 + nums[i]；
取两种选拔里数值更大的看成money。
材干3.2 转动更新DP情状变量
完成money估量后，刷新两个情状变量，为下一间房屋遍历作念准备：
1. f1 赋值为原本的f2：下一轮中，f1代表「不偷现时i号房」的最大收益；
2. f2 赋值为本轮算出的money：下一轮中，f2代表「偷现时i号房」的最大收益。
材干4：遍历一谈房屋后输出收尾
轮回收场后，f2保存的是遍历到终末一间房屋、包含偷终末一间决策的全局最大总金额，径直复返f2看成谜底。
三、工夫复杂度、稀奇空间复杂度分析
1. 工夫复杂度 O(n)
n为房屋总和，算法仅现实一次单层for轮回，轮回现实次数碰巧n-1次；
轮回里面仅包含神色相比、肤浅四则运算、大小相比，总计操作齐是常数工夫O(1)；
无嵌套轮回、无排序、无递归，合座工夫复杂度线性O(n)，不错随和题目n≤100000的数据领域。
2. 稀奇空间复杂度 O(1)
输入的nums、colors属于题目给定输入数组，不计入算法稀奇空间；
算法里面仅经久开导3个固定变量：f1、f2、money，变量数目不随房屋数目n变化；
莫得创建DP数组、切片、哈希表等随n扩容的数据结构；
仅使用常数级临时存储空间，稀奇空间复杂度为O(1)。
Go圆善代码如下：
package main
import (
"fmt"
)
func rob(nums []int， colors []int)int64 {
iflen(nums) == 0 {
return0
}
f1 := int64(0)
f2 := int64(nums[0])
n := len(nums)
for i := 1; i
var money int64
if colors[i] != colors[i-1] {
money = f2 + int64(nums[i])
} else {
if f1+int64(nums[i]) > f2 {
money = f1 + int64(nums[i])
} else {
money = f2
}
}
f1 = f2
f2 = money
}
return f2
}
func main {
nums := []int{10， 1， 3， 9}
colors := []int{1， 1， 1， 2}
result := rob(nums， colors)
fmt.Println(result)
}
Python圆善代码如下：
# -*-coding:utf-8-*-
from typing import List
class Solution:
def rob(self， nums: List[int]， colors: List[int]) -> int:
iflen(nums) == 0:
return0
f1 = 0
f2 = nums[0]
n = len(nums)
for i in range(1， n):
if colors[i] != colors[i-1]:
money = f2 + nums[i]
else:
money = max(f1 + nums[i]， f2)
f1 = f2
f2 = money
return f2
if __name__ == "__main__":
nums = [10， 1， 3， 9]
colors = [1， 1， 1， 2]
result = Solution.rob(nums， colors)
print(result)
C++圆善代码如下：
#include
#include
#include
using namespace std;
long long rob(vector& nums， vector& colors) {
if (nums.empty) {
return0;
}
long long f1 = 0;
long long f2 = nums[0];
int n = nums.size;
for (int i = 1; i
long long money;
if (colors[i] != colors[i-1]) {
money = f2 + nums[i];
} else {
money = max(f1 + nums[i]， f2);
}
f1 = f2;
f2 = money;
}
return f2;
}
int main {
vector nums = {10， 1， 3， 9};
vector colors = {1， 1， 1， 2};
long long result = rob(nums， colors);
cout
return0;
}
咱们确信东谈主工智能为平素东谈主提供了一种“增强器用”，并起劲于于共享全标的的AI学问。在这里，您不错找到最新的AI科普著述、器用评测、普及收尾的阴私以及行业洞悉。
迎接关怀“福大大架构师逐日一题”，发音问可获取口试尊府凤凰彩票_凤凰彩首页，让AI助力您的改日发展。