leetExpert
Practice

House Robber

Module 24 · Dynamic Programming

Problem

Given an array nums representing the amount of money in each house along a street, determine the maximum amount you can rob without robbing two adjacent houses (robbing adjacent houses trips the alarm). (LeetCode 198.)

Examples

Example 1

Inputnums = [1,2,3,1]Output4

Explanation. rob house 0 and house 2: 1 + 3 = 4

Example 2

Inputnums = [2,7,9,3,1]Output12

Explanation. rob houses 0, 2, 4: 2 + 9 + 1 = 12

Constraints

1 ≤ nums.length ≤ 100, values in [0, 400].

Attempt it first

Same 1D shape as Climbing Stairs — dp[i] depends on dp[i-1] and dp[i-2] — but the combining operator changes, because this problem asks for a MAXIMUM, not a count. Before opening anything, think through what genuine CHOICE exists at house i, and why the adjacency constraint means that choice has a direct consequence for what's available at house i-1.