What is Dynamic Programming

Dynamic Programming (DP) solves a problem faster than brute force by caching the answers to subproblems the recursive brute-force approach would otherwise recompute exponentially many times, then reusing those cached answers to assemble the final result in polynomial time.

Recognize the pattern

• The problem asks to optimize (min/max/count ways) over a sequence of choices — not "find one arrangement" but "find the best/count of arrangements."
• A brute-force recursive solution exists whose recursion tree has repeated calls with identical arguments (overlapping subproblems).
• The optimal answer to the whole problem can be built purely from optimal answers to strictly smaller instances (optimal substructure) — no need to know how a subproblem's optimum was achieved, only its value.
• Keywords: "minimum/maximum number of ways," "longest/shortest," "can we partition," "count distinct ways."

Brute force → optimal

Take computing the n-th Fibonacci number, Fib(n) = Fib(n-1) + Fib(n-2), Fib(0)=0, Fib(1)=1.

Brute-force recursion: call Fib(n-1) and Fib(n-2) directly, no caching. The number of calls grows exponentially, because fib(2), fib(1), etc. get recomputed from scratch every time they appear in the tree. O(2^n) is the standard loose upper bound quoted for this recursion; the exact growth rate is smaller and is derived precisely below. Space is O(n) for the call stack.

Optimal (DP): cache each Fib(k) the first time it's computed. Each of the n distinct subproblems is now solved once in O(1) work, giving O(n) time. Two equivalent ways to realize this:

• Top-down with memoization — keep the natural recursion, add an array/map cache; before recursing, check the cache.
• Bottom-up with tabulation — no recursion; fill a table from the smallest index upward, since each entry only needs the two before it.

Complexity, derived

Brute force: let C(n) be the exact number of calls to compute Fib(n). C(n) = C(n-1) + C(n-2) + 1, with C(0)=C(1)=1 (the "+1" counts the call itself). This is the same shape as the Fibonacci recurrence, so it has the same growth rate: C(n) = Θ(φ^n), where φ = (1+√5)/2 ≈ 1.618. This is the tight bound — the tighter, more informative fact than the loose O(2^n) ceiling mentioned above, and the two differ by an exponential factor as n grows (φ^n ≪ 2^n). Space is O(n) for the deepest recursion stack.

Memoized / tabulated: there are exactly n distinct subproblems (Fib(0) … Fib(n)). Each is computed exactly once, and each computation does O(1) work (one addition, one/two cache lookups). Total work = n subproblems × O(1) each = O(n) time. Space is O(n) for the cache/table (top-down also pays O(n) call-stack depth); bottom-up tabulation can be shrunk to O(1) space by keeping only the last two values, since Fib(k) only ever depends on Fib(k-1) and Fib(k-2).

Traced worked example — Fib(6), bottom-up

Each cell after the first two is dp[i] = dp[i-1] + dp[i-2]: dp[2]=1+0, dp[3]=1+1, dp[4]=2+1, dp[5]=3+2, dp[6]=5+3=8. That is five additions total (one per computed cell dp[2]..dp[6]). Compare against the brute-force call count using C(n)=C(n-1)+C(n-2)+1, C(0)=C(1)=1: C(2)=3, C(3)=5, C(4)=9, C(5)=15, C(6)=25 calls — not the loose 2^6=64 ceiling, which is a valid but slack upper bound, not the exact count for this tree.

Pitfalls

• Wrong state definition: if the DP state doesn't capture everything needed to make future decisions (e.g. forgetting a "remaining capacity" dimension), memoized answers become wrong, not just slow.
• Recursion depth in memoization: a naive top-down recursion for large n (e.g. n = 10^6) can blow the call stack; bottom-up tabulation or an explicit stack avoids this.
• Forgetting base cases or off-by-one indices when translating the recurrence into array indices.
• Over-allocating space: using an O(n) or O(n·m) table when the recurrence only ever looks back a constant number of steps (rolling-array optimization applies, as with Fibonacci's O(1)-space version).
• Confusing a loose asymptotic bound with an exact count: quoting O(2^n) for naive Fibonacci is a correct but slack ceiling — the exact call count follows C(n)=C(n-1)+C(n-2)+1 and grows as the tighter Θ(φ^n); don't treat the loose bound as the derived answer.

When to use / when NOT

Use DP when the problem has both overlapping subproblems and optimal substructure — it turns exponential brute force into polynomial time at the cost of extra memory.

vs. plain (greedy) recursion / divide-and-conquer: divide-and-conquer (e.g. merge sort) splits into disjoint subproblems, so there's nothing to cache — adding memoization there wastes memory for no speedup. Use DP specifically when subproblems overlap.

vs. Greedy: greedy makes one irrevocable locally-optimal choice per step and never revisits it — O(n) or O(n log n), no extra space for a table, but only correct when the problem provably has the greedy-choice property. DP is safer (explores/reuses all subproblem outcomes) but costs more time and space; prefer greedy when you can prove it's optimal, DP when you can't or when counting all ways.

vs. Backtracking: backtracking enumerates actual configurations (every valid arrangement), so reach for it when the problem asks you to list the solutions or when the constraints are irregular enough that no compact state captures them. DP applies precisely when you need only the aggregate optimum/count and the same subproblem recurs — then DP collapses backtracking's exponential enumeration into |states| work.

Java: brute force vs memoized vs tabulated

class Fibonacci {
  // Brute force: exact call count C(n)=C(n-1)+C(n-2)+1 = Theta(phi^n);
  // O(2^n) is the loose textbook ceiling. Space: O(n) call stack.
  static long fibBrute(int n) {
    if (n <= 1) return n;
    return fibBrute(n - 1) + fibBrute(n - 2);
  }

  // Top-down memoization: O(n) time, O(n) space
  static long fibMemo(int n, long[] cache) {
    if (n <= 1) return n;
    if (cache[n] != -1) return cache[n];
    cache[n] = fibMemo(n - 1, cache) + fibMemo(n - 2, cache);
    return cache[n];
  }

  // Bottom-up tabulation, rolled to O(1) space
  static long fibTab(int n) {
    if (n <= 1) return n;
    long prev2 = 0, prev1 = 1;
    for (int i = 2; i <= n; i++) {
      long cur = prev1 + prev2;
      prev2 = prev1;
      prev1 = cur;
    }
    return prev1;
  }
}

Takeaways

• DP = brute-force recursion + caching, applicable exactly when subproblems overlap and the problem has optimal substructure.
• Memoization (top-down) and tabulation (bottom-up) compute the same n subproblems; tabulation avoids recursion overhead and often permits O(1) space via rolling variables.
• Always derive complexity as (number of distinct subproblems) × (work per subproblem) — for Fibonacci that's n × O(1) = O(n), versus the brute-force call count C(n)=Θ(φ^n) (exactly 25 calls for Fib(6), far below the loose O(2^n)=64 ceiling).
• DP is not free: it trades memory (and design effort in choosing the right state) for time; when subproblems don't overlap, plain divide-and-conquer is simpler and equally fast.

Recall: Why does naive recursive Fibonacci take exponential time while the memoized version takes linear time, in terms of the number of distinct subproblems?

Adapted from Grokking Dynamic Programming Patterns (Educative) and standard CLRS treatment of overlapping subproblems and optimal substructure.