LeetCode算法题(Go语言实现)_61
题目
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
一、代码实现（动态规划优化）
func rob(nums []int) int {prev, curr := 0, 0for _, num := range nums {prev, curr = curr, max(curr, prev + num)}return curr
}func max(a, b int) int {if a > b {return a}return b
}
二、算法分析
1. 核心思路
- 滚动变量优化：仅维护前两个状态（前前最大值和前一最大值）
- 状态转移方程：当前最大值 = max(前一最大值, 前前最大值 + 当前房屋金额)
- 贪心选择：每一步选择局部最优解推进全局最优解
2. 关键步骤
- 初始化状态：prev=0（前前状态），curr=0（前一状态）
- 遍历房屋：
- 计算当前房屋两种决策的最大值
- 滚动更新前两个状态值
- 结果返回：最终curr即为全局最优解
3. 复杂度
| 指标 | 值 | 说明 |
|---|---|---|
| 时间复杂度 | O(n) | 线性遍历所有房屋 |
| 空间复杂度 | O(1) | 仅使用两个临时变量 |
三、图解示例
四、边界条件与扩展
1. 特殊场景验证
- 空数组：返回0
- 单房屋：直接返回该房屋金额
- 双房屋：返回金额较大值
- 全零数组：正确返回0
- 交替大数：正确选择非相邻房屋
2. 扩展应用
- 网络安全：选择不冲突节点进行渗透测试
- 资源分配：优化不重叠任务的收益
- 路径规划：寻找收益最大的不连续路径
3. 多语言实现
class Solution {public int rob(int[] nums) {int prev = 0, curr = 0;for (int num : nums) {int temp = Math.max(curr, prev + num);prev = curr;curr = temp;}return curr;}
}
class Solution:def rob(self, nums: List[int]) -> int:prev, curr = 0, 0for num in nums:prev, curr = curr, max(curr, prev + num)return curr
五、总结与优化
1. 算法对比
| 方法 | 优势 | 适用场景 |
|---|---|---|
| 动态规划 | 时间复杂度最优 | 常规场景 |
| 递归+记忆化 | 代码直观 | 教学演示 |
| 矩阵快速幂 | O(log n)时间复杂度 | 极大n值计算 |
2. 工程优化
- 循环展开：手动展开循环减少分支判断
- SIMD指令：利用并行计算加速向量运算
- 预计算缓存：存储常用结果减少重复计算
3. 扩展方向
- 环形房屋：处理首尾相连的特殊情况
- 多维约束：考虑时间、空间等多维度限制
- 概率模型：引入成功概率的随机决策模型