执行过程
创建 DP 表格:共有 5 间房。dp[i] 表示看完第 i 间房后,最多能拿多少钱。
before
nums=[5, 1, 6, 10, 2]
高亮: {"objects": ["arr:nums", "dp:table"], "indices": {"arr:nums": [0], "dp:table": [0]}}
💡 先把输入排成一排,再从左到右填 DP 表格。
🧠 每到一间房,都只做一个选择:跳过它,或者偷它。因为相邻房子不能同时选,偷当前房时只能接在 dp[i-2] 后面。
第 0 间房没有左邻选择冲突:偷它可以拿 5,跳过是 0。
before
i=0
nums[i]=5
skip_current=0
take_current=5
高亮: {"objects": ["arr:nums", "dp:table"], "indices": {"arr:nums": [0], "dp:table": [0]}}
💡 第一间房之前没有历史选择,直接比较偷和不偷。
写入 dp[0] = 5(偷当前房)。
after
dp_idx=0
dp_val=5
choice='偷当前房'
高亮: {"objects": ["arr:nums", "dp:table"], "indices": {"arr:nums": [0], "dp:table": [0]}}
💡 把当前最优结果记下来,后面的房屋会继续引用这个结果。
读取 dp[0]=5。第 1 间房如果要偷,就不能同时偷第 0 间。
before
i=1
nums[i]=1
dp[i-1]=5
高亮: {"objects": ["arr:nums", "dp:table"], "indices": {"arr:nums": [1], "dp:table": [0, 1]}}
💡 两间相邻房只能选一边,所以第 1 格只需要和第 0 格比较。
比较:跳过当前房得到 5;偷当前房得到 1。
before
skip_current=5
take_current=1
高亮: {"objects": ["arr:nums", "dp:table"], "indices": {"arr:nums": [1], "dp:table": [0, 1]}}
💡 DP 的选择不是'看到大数字就拿',而是比较两条合法路线的总金额。
写入 dp[1] = 5(跳过当前房)。
after
dp_idx=1
dp_val=5
choice='跳过当前房'
高亮: {"objects": ["arr:nums", "dp:table"], "indices": {"arr:nums": [1], "dp:table": [1]}}
💡 把当前最优结果记下来,后面的房屋会继续引用这个结果。
读取 dp[1]=5(跳过当前房)和 dp[0]=5(偷当前房前的安全位置)。
before
i=2
nums[i]=6
dp[i-2]=5
dp[i-1]=5
高亮: {"objects": ["arr:nums", "dp:table"], "indices": {"arr:nums": [2], "dp:table": [0, 1, 2]}}
💡 偷第 i 间房时,第 i-1 间必须跳过,所以只能加上 dp[i-2]。
比较:跳过当前房得到 5;偷当前房得到 dp[0] + nums[2] = 5 + 6 = 11。
before
skip_current=5
take_current=11
高亮: {"objects": ["arr:nums", "dp:table"], "indices": {"arr:nums": [2], "dp:table": [0, 1, 2]}}
💡 每一格都保存到当前位置的最好结果,不需要记住具体偷了哪些房。
写入 dp[2] = 11(偷当前房)。
after
dp_idx=2
dp_val=11
choice='偷当前房'
高亮: {"objects": ["arr:nums", "dp:table"], "indices": {"arr:nums": [2], "dp:table": [2]}}
💡 把当前最优结果记下来,后面的房屋会继续引用这个结果。
读取 dp[2]=11(跳过当前房)和 dp[1]=5(偷当前房前的安全位置)。
before
i=3
nums[i]=10
dp[i-2]=5
dp[i-1]=11
高亮: {"objects": ["arr:nums", "dp:table"], "indices": {"arr:nums": [3], "dp:table": [1, 2, 3]}}
💡 偷第 i 间房时,第 i-1 间必须跳过,所以只能加上 dp[i-2]。
比较:跳过当前房得到 11;偷当前房得到 dp[1] + nums[3] = 5 + 10 = 15。
before
skip_current=11
take_current=15
高亮: {"objects": ["arr:nums", "dp:table"], "indices": {"arr:nums": [3], "dp:table": [1, 2, 3]}}
💡 每一格都保存到当前位置的最好结果,不需要记住具体偷了哪些房。
写入 dp[3] = 15(偷当前房)。
after
dp_idx=3
dp_val=15
choice='偷当前房'
高亮: {"objects": ["arr:nums", "dp:table"], "indices": {"arr:nums": [3], "dp:table": [3]}}
💡 把当前最优结果记下来,后面的房屋会继续引用这个结果。
读取 dp[3]=15(跳过当前房)和 dp[2]=11(偷当前房前的安全位置)。
before
i=4
nums[i]=2
dp[i-2]=11
dp[i-1]=15
高亮: {"objects": ["arr:nums", "dp:table"], "indices": {"arr:nums": [4], "dp:table": [2, 3, 4]}}
💡 偷第 i 间房时,第 i-1 间必须跳过,所以只能加上 dp[i-2]。
比较:跳过当前房得到 15;偷当前房得到 dp[2] + nums[4] = 11 + 2 = 13。
before
skip_current=15
take_current=13
高亮: {"objects": ["arr:nums", "dp:table"], "indices": {"arr:nums": [4], "dp:table": [2, 3, 4]}}
💡 每一格都保存到当前位置的最好结果,不需要记住具体偷了哪些房。
写入 dp[4] = 15(跳过当前房)。
after
dp_idx=4
dp_val=15
choice='跳过当前房'
高亮: {"objects": ["arr:nums", "dp:table"], "indices": {"arr:nums": [4], "dp:table": [4]}}
💡 把当前最优结果记下来,后面的房屋会继续引用这个结果。
DP 表格填完,最后一格 dp[4] = 15,这就是最大金额。
🧠 最后一格表示'看完所有房屋后,能拿到的最大金额'。