LeetCode 198 House Robber - Why Greedy Fails

A common greedy approach: sum values at odd positions, sum values at even positions, take the max. This fails. Example: $a = [2, 1, 1, 2]$. Odd-position sum = $a_1 + a_3 = 3$. Even-position sum = $a_2 + a_4 = 3$.

But picking houses $1$ and $4$ gives $a_1 + a_4 = 4$, which is better than both. The greedy approach fails because sometimes skipping an odd-positioned house for a larger even-positioned one (or vice versa) gives a better total. You can't decide locally. You need the global picture. This is why DP is required. The next unit shows how to set up the state.