打家劫舍 (0198_house_robber)

标签: dynamic_programming · 难度: MEDIUM

输入

nums:
5
1
6
10
2
DP 表:
0房屋金额 55
1房屋金额 15
2房屋金额 611
3房屋金额 1015
4房屋金额 215

执行过程

Step 1 · dp_init
创建 DP 表格:共有 5 间房。dp[i] 表示看完第 i 间房后,最多能拿多少钱。

before

nums=[5, 1, 6, 10, 2]

after

高亮: {"objects": ["arr:nums", "dp:table"], "indices": {"arr:nums": [0], "dp:table": [0]}}
💡 先把输入排成一排,再从左到右填 DP 表格。
🧠 每到一间房,都只做一个选择:跳过它,或者偷它。因为相邻房子不能同时选,偷当前房时只能接在 dp[i-2] 后面。
Step 2 · choose_transition
第 0 间房没有左邻选择冲突:偷它可以拿 5,跳过是 0。

before

i=0 nums[i]=5 skip_current=0 take_current=5

after

高亮: {"objects": ["arr:nums", "dp:table"], "indices": {"arr:nums": [0], "dp:table": [0]}}
💡 第一间房之前没有历史选择,直接比较偷和不偷。
Step 3 · dp_write
写入 dp[0] = 5(偷当前房)。

before

dp_idx=0

after

dp_idx=0 dp_val=5 choice='偷当前房'
高亮: {"objects": ["arr:nums", "dp:table"], "indices": {"arr:nums": [0], "dp:table": [0]}}
💡 把当前最优结果记下来,后面的房屋会继续引用这个结果。
Step 4 · dp_read
读取 dp[0]=5。第 1 间房如果要偷,就不能同时偷第 0 间。

before

i=1 nums[i]=1 dp[i-1]=5

after

高亮: {"objects": ["arr:nums", "dp:table"], "indices": {"arr:nums": [1], "dp:table": [0, 1]}}
💡 两间相邻房只能选一边,所以第 1 格只需要和第 0 格比较。
Step 5 · choose_transition
比较:跳过当前房得到 5;偷当前房得到 1。

before

skip_current=5 take_current=1

after

高亮: {"objects": ["arr:nums", "dp:table"], "indices": {"arr:nums": [1], "dp:table": [0, 1]}}
💡 DP 的选择不是'看到大数字就拿',而是比较两条合法路线的总金额。
Step 6 · dp_write
写入 dp[1] = 5(跳过当前房)。

before

dp_idx=1

after

dp_idx=1 dp_val=5 choice='跳过当前房'
高亮: {"objects": ["arr:nums", "dp:table"], "indices": {"arr:nums": [1], "dp:table": [1]}}
💡 把当前最优结果记下来,后面的房屋会继续引用这个结果。
Step 7 · dp_read
读取 dp[1]=5(跳过当前房)和 dp[0]=5(偷当前房前的安全位置)。

before

i=2 nums[i]=6 dp[i-2]=5 dp[i-1]=5

after

高亮: {"objects": ["arr:nums", "dp:table"], "indices": {"arr:nums": [2], "dp:table": [0, 1, 2]}}
💡 偷第 i 间房时,第 i-1 间必须跳过,所以只能加上 dp[i-2]。
Step 8 · choose_transition
比较:跳过当前房得到 5;偷当前房得到 dp[0] + nums[2] = 5 + 6 = 11。

before

skip_current=5 take_current=11

after

高亮: {"objects": ["arr:nums", "dp:table"], "indices": {"arr:nums": [2], "dp:table": [0, 1, 2]}}
💡 每一格都保存到当前位置的最好结果,不需要记住具体偷了哪些房。
Step 9 · dp_write
写入 dp[2] = 11(偷当前房)。

before

dp_idx=2

after

dp_idx=2 dp_val=11 choice='偷当前房'
高亮: {"objects": ["arr:nums", "dp:table"], "indices": {"arr:nums": [2], "dp:table": [2]}}
💡 把当前最优结果记下来,后面的房屋会继续引用这个结果。
Step 10 · dp_read
读取 dp[2]=11(跳过当前房)和 dp[1]=5(偷当前房前的安全位置)。

before

i=3 nums[i]=10 dp[i-2]=5 dp[i-1]=11

after

高亮: {"objects": ["arr:nums", "dp:table"], "indices": {"arr:nums": [3], "dp:table": [1, 2, 3]}}
💡 偷第 i 间房时,第 i-1 间必须跳过,所以只能加上 dp[i-2]。
Step 11 · choose_transition
比较:跳过当前房得到 11;偷当前房得到 dp[1] + nums[3] = 5 + 10 = 15。

before

skip_current=11 take_current=15

after

高亮: {"objects": ["arr:nums", "dp:table"], "indices": {"arr:nums": [3], "dp:table": [1, 2, 3]}}
💡 每一格都保存到当前位置的最好结果,不需要记住具体偷了哪些房。
Step 12 · dp_write
写入 dp[3] = 15(偷当前房)。

before

dp_idx=3

after

dp_idx=3 dp_val=15 choice='偷当前房'
高亮: {"objects": ["arr:nums", "dp:table"], "indices": {"arr:nums": [3], "dp:table": [3]}}
💡 把当前最优结果记下来,后面的房屋会继续引用这个结果。
Step 13 · dp_read
读取 dp[3]=15(跳过当前房)和 dp[2]=11(偷当前房前的安全位置)。

before

i=4 nums[i]=2 dp[i-2]=11 dp[i-1]=15

after

高亮: {"objects": ["arr:nums", "dp:table"], "indices": {"arr:nums": [4], "dp:table": [2, 3, 4]}}
💡 偷第 i 间房时,第 i-1 间必须跳过,所以只能加上 dp[i-2]。
Step 14 · choose_transition
比较:跳过当前房得到 15;偷当前房得到 dp[2] + nums[4] = 11 + 2 = 13。

before

skip_current=15 take_current=13

after

高亮: {"objects": ["arr:nums", "dp:table"], "indices": {"arr:nums": [4], "dp:table": [2, 3, 4]}}
💡 每一格都保存到当前位置的最好结果,不需要记住具体偷了哪些房。
Step 15 · dp_write
写入 dp[4] = 15(跳过当前房)。

before

dp_idx=4

after

dp_idx=4 dp_val=15 choice='跳过当前房'
高亮: {"objects": ["arr:nums", "dp:table"], "indices": {"arr:nums": [4], "dp:table": [4]}}
💡 把当前最优结果记下来,后面的房屋会继续引用这个结果。
Step 16 · return
DP 表格填完,最后一格 dp[4] = 15,这就是最大金额。

before

after

result=15
🧠 最后一格表示'看完所有房屋后,能拿到的最大金额'。