DP Foundations & 1-D DP

Why DP is different from everything before it

Every topic so far has given you a recognizable shape: two pointers converging, a window sliding, a stack tracking monotonicity. Dynamic Programming gives you no shape at all — it gives you a property your problem must have, and asks you to derive the shape yourself. That derivation, done live, under time pressure, is the actual skill being tested. Candidates who "know DP" from having seen 100 problems but can't derive a recurrence for problem 101 are exactly who this subtopic is designed to fix.

The good news: the property is simple, and the derivation process is mechanical once you drill it.

The two properties that make a problem DP

A problem is a DP candidate if and only if it has both of these:

1. Optimal substructure — the optimal answer to the whole problem can be built from optimal answers to its subproblems. (Contrast with problems where the locally-optimal choice at each step doesn't compose into a global optimum — that's the boundary with Greedy, covered later in the roadmap.)
2. Overlapping subproblems — the naive recursive solution calls itself with the same arguments multiple times. If every recursive call has distinct arguments, you have plain recursion or divide-and-conquer (like merge sort), not DP — memoizing buys you nothing.

You already have the tool to check property 2: draw the recursion tree (from the Big-O & Complexity Analysis topic) and look for repeated nodes. Naive Fibonacci is the canonical example — fib(5) calls fib(3) twice, fib(2) three times, and so on, which is exactly why it blows up to O(2ⁿ) despite there only being O(n) distinct subproblems.

The derivation process, step by step

This is the process you should run, out loud, in every interview where DP is even a possibility:

1. Write the brute-force recursive solution first. Don't try to jump straight to a DP table — define a recursive function that tries all choices at each step and returns the best result. This is usually a direct translation of the problem statement, and it's the same recursive-exploration instinct you built in Backtracking.
2. Identify the state. What are the changing arguments to your recursive function? Ignore arguments that never change across calls. The state is the minimal set of values needed to answer "what happens from here" — nothing more, nothing less. Too few dimensions and you get wrong answers (you've conflated distinct subproblems); too many and you waste memory and time recomputing states that were actually identical.
3. Write the state definition in one sentence. This is the single most important habit to build, and the one most candidates skip. Before writing any code, say: "dp[i] is the [maximum profit / minimum cost / number of ways / longest length] of [doing X] using [the first i elements / ending at index i / starting from index i]." If you can't write this sentence precisely, you don't understand your own recurrence yet — and you will get the base cases or the direction of iteration wrong.
4. Derive the transition. Given the state definition, ask: "what are all the choices I can make at this state, and how does each choice relate to a smaller/simpler state?" This is where the recurrence — dp[i] = f(dp[i-1], dp[i-2], ...) — comes from. It falls directly out of the choices enumerated in your brute-force recursion.
5. Identify the base case(s). The smallest state(s) that can't be broken down further — usually dp[0] or dp[-1]/an empty-input sentinel.
6. Decide the iteration order. You must compute a state's dependencies before the state itself. For 1-D problems this is almost always "increasing index," but it's worth stating explicitly, because it stops being obvious once you get to Interval DP later in this topic.

Memoization (top-down) vs. tabulation (bottom-up)

Both implement the exact same recurrence — the difference is direction and mechanics, not correctness.

	Memoization (top-down)	Tabulation (bottom-up)
Structure	Recursive function + cache (dict or array)	Iterative loop filling an array
Computes	Only the states actually needed for the answer	Every state in the table, in order
Base cases	Handled as early-return guard clauses	Pre-filled before the main loop
Stack usage	O(depth) call stack — can overflow on deep recursion (e.g. large n in Python without raising the recursion limit)	O(1) beyond the table itself
Easiest to derive from	The brute-force recursion — minimal code changes (add a cache)	Requires you to already know the full dependency order
Typical interview move	Start here — fastest to get correct	Convert to this once the recurrence is validated, especially if space optimization is asked for

Interview default: derive with memoization, then convert to tabulation if the interviewer asks for further optimization (they usually will, particularly for the O(1)-space follow-up below). Memoization is safer to derive correctly first because it's a minimal edit to code you already trust; tabulation is more common as the final, polished answer because it avoids recursion overhead and stack-depth risk entirely.

The shape of classic 1-D DP problems

Without spoiling the specific problems below, the 1-D DP family you're about to drill shares one of two shapes:

• "Take or skip" at each position, where the recurrence looks at a small, fixed window of previous states (dp[i-1], dp[i-2], ...) and the decision is binary — this is the shape behind counting-paths-through-a-sequence and non-adjacent-selection problems.
• "Best result ending at position i, extending or restarting", where you track the best answer ending exactly at index i (not "using the first i elements") and take a running maximum/minimum across all i — this is the shape behind maximum-subsequence-value problems, and it generalizes to a genuinely different (and much harder) recurrence when the underlying operation isn't associative in the way addition is.

Recognizing which of these two shapes (or a string-parsing variant of the first) applies is 80% of solving any problem in this subtopic.

Space optimization: the rolling array

Once your transition only depends on a constant number of previous states (say, dp[i-1] and dp[i-2]), you don't need the full array — keep only the last k values in scalar variables and shift them each iteration. This turns O(n) space into O(1) space, and is one of the most common "can you optimize the space?" follow-ups in a Senior-level loop.

The trade-off: you lose the ability to reconstruct the full sequence of choices afterward (relevant if the problem asks you to return the actual path, not just its value) and the code is marginally less readable. State that trade-off out loud when you make it.

Complexity

For a 1-D DP with n states and O(1) transition cost per state (looking at a constant number of previous states), you get O(n) time. If the transition requires scanning back over all previous states (dp[i] = f(dp[0], dp[1], ..., dp[i-1])), that's O(n) work per state, giving O(n²) overall — a common trap when a problem looks 1-D but the recurrence secretly needs a full backward scan (this shows up in the increasing-subsequence family). Space is O(n) for the table, reducible to O(1) or O(k) via rolling arrays when the transition window is bounded.

Common pitfalls

• Vague state definition. If you can't say "dp[i] means ___" in one precise sentence, you will get the recurrence or base case wrong. This is the #1 cause of DP bugs — more than off-by-one errors.
• Off-by-one in indices, especially with string/array problems. Deciding whether dp[i] represents "the first i characters" or "the character at index i" changes every single index in your recurrence. Pick one convention and stay consistent; many experienced engineers pad with a dummy row representing the empty prefix (dp[0] = ...) specifically to avoid special-casing the empty case.
• Wrong base case for counting problems. For "number of ways" problems, the base case for an empty input is usually 1 (there's exactly one way to do nothing), not 0 — get this backwards and every count downstream is zero.
• Forgetting integer overflow in counting DP — less of a concern in Python, but state it explicitly if asked to reason about a lower-level language; large "number of ways" counts on n in the hundreds can exceed 32-bit range fast, which is why LeetCode counting problems often ask you to return the count modulo 10^9 + 7.
• Treating a Greedy-solvable problem as DP (or vice versa). If you can prove the locally optimal choice is always part of some globally optimal solution, you don't need to explore both "take" and "skip" branches — you're looking at Greedy, not DP. If you're not sure such a proof exists, default to DP: it's always correct, just potentially slower.