Pattern visualizer
House Robber
Because you can never rob two adjacent houses, the best score at house i can only be built from a house two or more steps back — so every house's best answer is computed once and then reused, never redone. Every house poses the same binary choice: SKIP it and keep rob[i-1], or TAKE its cash plus the best from two houses back, rob[i-2] + nums[i]. Fill rob[] left to right and each entry becomes a solved subproblem the next house reuses — that reuse is the whole trick of DP. Animated on: Rob houses with values [2, 7, 9, 3, 1] without robbing two adjacent houses — maximize the loot..
Bottom-up DP over adjacent-house choices
Houses [2, 7, 9, 3, 1], and rob[i] will mean 'the most loot possible from the first i+1 houses'. Base case: with only house 0 in play, rob[0] = 2.
1FUNCTION rob(nums):2 rob[0] = nums[0]3 rob[1] = the larger of nums[0] and nums[1]4 FOR i from 2 to n-1:5 take = rob[i-2] + nums[i]6 skip = rob[i-1]7 rob[i] = the larger of skip and take8 RETURN rob[n-1]
← / → step · space play · Home restart