Master the House Robber Problem with Dynamic Programming

Problem Statement

Given an array of non‑negative integers where each element represents the amount of money in a house, determine the maximum amount that can be stolen without robbing two adjacent houses on the same night.

Example

Input: [3,2,1,2]

Output: 5

Choosing houses 0 and 3 yields 5, which is better than the naive alternating choice that would only give 4.

Analysis

Because adjacent houses are mutually exclusive, the problem cannot be solved by a fixed‑interval pattern; instead it requires considering two cases for each house: either it is robbed (and the previous house cannot be) or it is skipped.

Dynamic Programming Solution

Define dp[i] as the maximum amount that can be obtained from the first i+1 houses.

Recurrence: dp[i] = max(dp[i-1], dp[i-2] + nums[i]) Base cases:

dp[0] = nums[0]

dp[1] = max(nums[0], nums[1])

This recurrence captures the two possibilities: skipping the current house ( dp[i-1]) or robbing it ( dp[i-2] + nums[i]).

Code Example

Conclusion

The House Robber problem is a textbook example of using dynamic programming to transform a combinatorial optimization problem into a linear‑time solution by building on previously computed sub‑problems.