← All patterns
24 / 32
Dynamic Programming

1D Dynamic Programming

When you see it

Signal words

If the prompt uses any of these, this pattern should come to mind first.

ways tomax / min over choicesclimbing stairshouse robberdecodelongest increasing
Practice

Drill this pattern with an AI trainer — reply only with Hint, Next, Lost, or paste your code.

Ask yourself

  1. Optimal/count over a 1D sequence of choices?
  2. Does the answer at i depend on a few earlier i’s?
  3. Define dp[i], a recurrence, and a base case.

Classic problem

House Robber (LeetCode 198) — given houses with nums[i] cash, take the maximum total without robbing two adjacent houses.

Input: nums = [2, 7, 9, 3, 1]

Output: 12 — rob houses 0 (2), 2 (9), and 4 (1), skipping the adjacent houses 1 and 3.

Watch it run

Common pitfalls

Wrong base cases / array size.

Reading dp[i-2] before it’s filled.