Optimization

Dynamic Programming

Optimization technique solving complex problems by breaking them into overlapping subproblems and caching results.

What is Dynamic Programming?

Dynamic Programming (DP) is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable to problems exhibiting overlapping subproblems and optimal substructure. Rather than recomputing subproblems, DP caches answers in memory. This can be done top-down with memoization (recursion + hashing) or bottom-up with tabulation (iterative array updates).

Key Characteristics:

  • Eliminates redundant overlapping computations.
  • Optimal substructure: overall solution built from local subproblem solutions.
  • Memoization: Top-Down recursion with lookup cache.
  • Tabulation: Bottom-Up iterative table updates.

Complexity Analysis

Avg Time Complexity: O(N) for linear sequence tabulation
Space Complexity: O(N) memory table size
Best Case: O(N)
Worst Case: O(N)

How it Works Step-by-Step

  1. State Definition: Define the state variables (e.g. DP[i] represents fib(i)).
  2. Base Cases: Initialize baseline states (e.g. DP[0] = 0, DP[1] = 1).
  3. State Transition: Define transition formula (e.g. DP[i] = DP[i-1] + DP[i-2]).
  4. Iterative Table Fill: Run a loop from i=2 to N, filling DP[i] using the transition.
  5. Return Result: Access DP[N] for the final solution.

Code Implementation

Worked Trace Example

Tabulating fib(4):
1. Initialize array DP size 5: DP = [0, 1, 0, 0, 0].
2. Compute DP[2] = DP[1] + DP[0] = 1 + 0 = 1. DP becomes [0, 1, 1, 0, 0].
3. Compute DP[3] = DP[2] + DP[1] = 1 + 1 = 2. DP becomes [0, 1, 1, 2, 0].
4. Compute DP[4] = DP[3] + DP[2] = 2 + 1 = 3. DP becomes [0, 1, 1, 2, 3].
Result: fib(4) = 3.

Ready to Understand Dynamic Programming Visually?

Don't just read about it. Launch our interactive, premium algorithm visualizer to step through calculations in real-time.

Launch Dynamic Programming Visualizer →