1-D Dynamic Programming

What it is

Dynamic programming solves a problem by breaking it into overlapping subproblems — unlike divide-and-conquer, where subproblems don't overlap. 1-D DP means the subproblem is indexed by a single variable (e.g. dp[i] = the answer considering only the first i elements).

The two implementations

• Top-down (memoization) — write the natural recursive solution, cache each dp[i] the first time it's computed, return the cached value on repeat calls.
• Bottom-up (tabulation) — build the dp array from the base case upward in a loop, avoiding recursion overhead entirely.

Recognizing the recurrence

The core step is expressing dp[i] in terms of smaller indices — e.g. climbing stairs: dp[i] = dp[i-1] + dp[i-2] (came from one step back or two). Once that recurrence is found, the implementation is largely mechanical.

Why backtracking comes first

Naive recursive backtracking re-solves the same subproblem exponentially many times; DP is that same recursive structure plus a cache (or an iterative rewrite) that turns exponential time into polynomial.