Chapter 1: The DP Mindset

If you have been grinding LeetCode and memorizing patterns like “when you see knapsack, use 2D DP,” you are not alone — and you are also not learning dynamic programming. You are learning pattern matching, which breaks the moment a problem does not fit a template you have seen before.

Dynamic programming is a problem-solving paradigm, not a bag of tricks. At its core, DP is about two ideas working together:

• Decomposition — break a large problem into smaller, similar subproblems.
• Reuse — store and reuse answers to those subproblems instead of recomputing them.

The most common misconception is that DP equals “recursion with caching.” Memoization is one implementation technique, not the definition. You can solve DP problems iteratively without any recursion at all. Conversely, adding a cache to a recursive function does not magically make it DP — the problem must first have the right structure.

DP is not about the table. It is about recognizing that a problem has reusable structure, then writing down what each state means and how states relate.

The Two Properties

Every DP problem has exactly two structural properties. If either is missing, you cannot apply dynamic programming — no matter how clever your memoization is.

1. Overlapping Subproblems

When you decompose the problem recursively, the same subproblems appear multiple times. Fibonacci is the canonical example. To compute fib(5), you need fib(4) and fib(3). But fib(4) also needs fib(3), and fib(3) appears again when computing fib(5) directly. The work is duplicated exponentially.

                    fib(5)
                   /      \
              fib(4)      fib(3)
             /    \       /    \
        fib(3) fib(2) fib(2) fib(1)
        /  \   /  \   /  \
   fib(2) fib(1) ...  ...  ...
   /  \
fib(1) fib(0)

Notice: fib(3) is computed 2 times, fib(2) is computed 3 times, fib(1) is computed 5 times.

Without caching, the naive recursive Fibonacci runs in O(2ⁿ) time because the recursion tree explodes with redundant calls. DP fixes this by computing each subproblem once and remembering the result.

2. Optimal Substructure

The optimal solution to the full problem can be built from optimal solutions to its subproblems. Formally: if you know the best answer for smaller instances, you can combine them to get the best answer for the current instance — without needing to reconsider earlier choices globally.

Example (has optimal substructure): Shortest path in a weighted graph. If the shortest path from A to C goes through B, then the A→B segment must itself be the shortest path from A to B. Otherwise, you could swap in a shorter segment and improve the full path.

Counter-example (no optimal substructure): Longest simple path in a general graph. Consider this graph:

    A --- B
     \   /
      \ /
       C

Longest path A → C might go A → B → C (length 2).
But the longest path A → B is A → C → B (length 2),
which is NOT a subpath of the A → B → C solution.

Subproblem solutions don't compose cleanly — longest path fails optimal substructure.

This is why not every recursive problem with a cache is DP. Longest path in a general graph can have overlapping subproblems but lacks optimal substructure, so the standard DP recurrence does not apply.

Top-Down vs Bottom-Up

Once you have identified overlapping subproblems and optimal substructure, you have two equivalent ways to compute answers: start from the big problem and recurse down (top-down), or start from the smallest cases and build up (bottom-up).

Top-Down (Memoization)

Write the natural recursive solution, then add a cache (array or hash map) keyed by subproblem parameters. Before computing, check the cache. After computing, store the result. You only visit subproblems that are actually needed — lazy evaluation.

fib(n):
  if n <= 1: return n
  if memo[n] exists: return memo[n]
  memo[n] = fib(n-1) + fib(n-2)
  return memo[n]

Bottom-Up (Tabulation)

Fill a table iteratively from base cases upward. You explicitly decide the fill order so that when you compute cell dp[i], all its dependencies are already computed. No recursion stack, no function call overhead.

dp[0] = 0
dp[1] = 1
for i = 2 to n:
  dp[i] = dp[i-1] + dp[i-2]
return dp[n]

Use the visualizer below to step through bottom-up Fibonacci tabulation. Watch how each cell depends on the two cells before it, and how the formula bar shows the recurrence in action.

Fibonacci Walkthrough with Code

Fibonacci is deliberately simple — that is the point. Every variant below solves the same problem; the difference is how efficiently they reuse work. Try running each variant in the editor. Brute force will time out for large n; the others finish instantly.

• Brute Force — pure recursion, O(2ⁿ) time. Shows why overlap matters.
• Memoized — top-down with a cache, O(n) time and O(n) space.
• Tabulation — bottom-up table fill, O(n) time and O(n) space.
• Space-Optimized — only keep the last two values, O(n) time and O(1) space.

Climbing Stairs

LeetCode 70: You are climbing a staircase with n steps. Each time you can climb 1 or 2 steps. How many distinct ways can you reach the top?

This problem is structurally identical to Fibonacci, but the story is different — and that is an important lesson. The same recurrence appears in many disguises. What matters is recognizing the underlying structure:

• State: which step you are standing on (i)
• Decision: take 1 step or 2 steps to arrive at step i
• Recurrence: dp[i] = dp[i-1] + dp[i-2]
• Base cases: dp[1] = 1, dp[2] = 2 (one way to reach step 1; two ways to reach step 2: 1+1 or 2)

The visualizer uses base cases dp[0] = 1 and dp[1] = 1, which is an equivalent indexing — the recurrence and dependencies are the same.

When to Suspect DP