Dynamic Programming Explained Through the Classic House Robber Problem

Dynamic programming (DP) is a technique that solves complex problems by breaking them into smaller overlapping sub-problems and storing their results to avoid redundant computation. The classic House Robber problem — finding the maximum money stealable from non-adjacent houses — illustrates this well, as a brute-force approach runs in O(2ⁿ) time and becomes impractical beyond ~50 elements. The key insight is that the optimal choice at any house depends only on the results from the previous two houses, yielding the recurrence dp[i] = max(dp[i-1], dp[i-2] + nums[i]). This reduces time complexity to O(n) and, by tracking just two variables instead of a full array, space complexity to O(1). The problem appears as LeetCode 198 and serves as a foundational example for learning DP patterns.