Include-or-Exclude DP

Foundations

In the first lesson, each slot added up the ways from the two before it. Now, what if each slot must choose instead, keeping the better of two options, where taking the current element rules out its neighbor?

Include-or-exclude DP gives each index one decision. Let best[i] be the best answer using elements 0 through i. Skipping nums[i] keeps best[i - 1]; taking it adds nums[i] to best[i - 2], the best that leaves its left neighbor out. The recurrence keeps the larger, and since it reads only the last two slots, two variables can replace the whole table.

Pick elements of nums = [7, 1, 5, 3, 6], never two neighbors, for the largest sum. best fills as 7, 7, 12, 12, 18: at index 2, taking 5 on top of best[0] = 7 beats skipping, and at index 4, taking 6 on top of best[2] = 12 makes 18. The chosen elements are 7, 5, and 6, at indexes 0, 2, and 4.

Case Scenario

House Robber is the same choice with houses for elements: nums[i] is the money in house i, and robbing two adjacent houses trips the alarm. Each house is robbed or skipped, so best[i] = max(best[i - 1], best[i - 2] + nums[i]). For nums = [2, 7, 9, 3, 1], robbing houses 0, 2, and 4 gives 2 + 9 + 1 = 12.

The direct approach tries both choices at every house: rob it and recurse past its neighbor, or skip it and recurse on the next. The same prefixes come up again and again, so the calls grow exponentially, about 1.6ⁿ, even though only n different subproblems exist: the best total over each prefix.