知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 55 - 打家劫舍 ## 题目(LeetCode 198) 不能偷相邻的房屋,求能偷到的最大金额。 ## 解法 ```java 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; } } ``` ## 复杂度 - 时间 O(n),空间 O(1) ## 一句话总结 每间房选择偷或不偷,dp[i] = max(dp[i-1], dp[i-2] + nums[i])。 ## 说明 打家劫舍是经典 DP 问题,当前滚动数组解法已是最优(O(n) 时间,O(1) 空间)。 > 💬 **Q:什么是滚动数组解法?** > > 当 dp 转移方程只依赖前面有限个状态时,不需要开整个数组,用几个变量"滚动"替代,空间从 O(n) 降到 O(1)。 > > 打家劫舍的转移:`dp[i] = max(dp[i-1], dp[i-2] + nums[i])`,只依赖前两个值。 > > ``` > 普通数组版(空间 O(n)): > nums = [2, 7, 9, 3, 1] > dp = [2, 7, 11, 10, 12] ← 开了长度 5 的数组 > > 滚动数组版(空间 O(1),只用两个变量): > 初始:prev2=0, prev1=0 > > i=0: cur = max(0, 0+2)=2 → prev2=0, prev1=2 > i=1: cur = max(2, 0+7)=7 → prev2=2, prev1=7 > i=2: cur = max(7, 2+9)=11 → prev2=7, prev1=11 > i=3: cur = max(11,7+3)=11 → prev2=11, prev1=11 > i=4: cur = max(11,11+1)=12 → prev2=11, prev1=12 > > 答案 prev1=12 ✓ > ``` > > 每一步算完 cur 后,prev2 和 prev1 往前"滚动"一格,旧值就不需要了。代码里的 `prev2 = prev1; prev1 = cur;` 就是这个滚动过程。 > > 适用条件:dp[i] 只依赖 dp[i-1] 和 dp[i-2](或有限个前驱状态)。爬楼梯、斐波那契也是同理。 常见变体: - **环形版(LeetCode 213)**:分两次 DP,一次不偷第一间,一次不偷最后一间,取最大值 - **树形版(LeetCode 337)**:树形 DP,每个节点返回 [偷, 不偷] 两种状态的最大值
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入