How does dynamic programming differ from plain recursion?
Dynamic programming solves a problem by reusing results from overlapping subproblems, while plain recursion may solve the same subproblem repeatedly. DP usually adds memoization or organizes computation in an order that stores each required result once.
Read full answerHide full answer
Applies tolanguage-independent (examples in Python 3.12)
Core Idea
For a problem such as computing Fibonacci numbers, define the state clearly:
-
dp[i]means the value of theith Fibonacci number. -
Recurrence:
dp[i] = dp[i - 1] + dp[i - 2]. -
Base cases:
dp[0] = 0anddp[1] = 1. -
Computation order: Calculate states from smaller indices to larger indices.
Dynamic programming requires two properties:
-
Overlapping subproblems: Different branches of the computation request the same states. For example, plain recursive Fibonacci repeatedly calculates
fib(3)andfib(2). -
Optimal substructure: A state’s answer can be constructed from answers to smaller states using the recurrence.
Difference from Recursion
Recursion and dynamic programming are not mutually exclusive. Recursion describes the control flow; DP describes how previously calculated states are reused.
For the Fibonacci example:
| Approach | Time | Space | When to use |
|---|---|---|---|
| Plain recursion | O(2^n) |
O(n) |
Small inputs or as a baseline when repeated-state reuse is unnecessary |
| Top-down DP with memoization | O(n) |
O(n) |
When dependencies are discovered naturally |
| Bottom-up DP | O(n) |
O(n) |
When dependencies can be calculated in order |
| Bottom-up with rolling variables | O(n) |
O(1) |
When only the previous two states are needed |
For plain recursive Fibonacci, the time is O(2^n) in the best, average, and worst cases because the recursion tree contains exponentially many calls. Its space is O(n) because the maximum recursion depth is O(n).
Memoized and table-based bottom-up Fibonacci both take O(n) time in all cases. Their space is O(n) because they retain O(n) states; retaining only the previous two states reduces auxiliary space to O(1). These complexities include the recursion stack where applicable but do not count the input itself.
Filled DP Table
For n = 5:
i |
dp[i] |
Calculation |
|---|---|---|
| 0 | 0 | Base case |
| 1 | 1 | Base case |
| 2 | 1 | 1 + 0 |
| 3 | 2 | 1 + 1 |
| 4 | 3 | 2 + 1 |
| 5 | 5 | 3 + 2 |
The table demonstrates why each state is calculated only once.
Common Pitfalls
-
Undefined state: Always specify exactly what
dp[i]ordp[i][j]represents. -
Incorrect base cases: They must cover every state that the recurrence cannot calculate.
-
Wrong computation order: Bottom-up dependencies must already be available.
-
Recursion depth: Top-down Fibonacci approaches Python’s default recursion limit for large
n; use an iterative version or an explicit stack. -
Unnecessary storage: If only a fixed number of previous states are needed, retain only those values.
-
Invalid input: A Fibonacci implementation should reject negative
nand handlen = 0andn = 1. Duplicates, sorted input, disconnected graphs, and cycles are not applicable to this problem. -
Integer overflow in other languages: Use a sufficiently large integer type for large results.
Interview Tips
Expect follow-up questions about choosing a suitable state, proving that the recurrence is correct, identifying overlapping subproblems and optimal substructure, selecting a computation order, and reducing space usage. Explain these points before discussing implementation details.