Dynamic Programming: From Memoization to Optimal Solutions

Master dynamic programming fundamentals including memoization, tabulation, and how to identify DP subproblems.

published: April 7, 2026 reading time: 12 min read author: GeekWorkBench

Dynamic Programming: From Memoization to Optimal Solutions

DP is one of those topics that separates candidates who can solve hard problems from those who freeze. The good news: once you see through the fog, the patterns click fast.

The core idea is simple: if your problem has optimal substructure (optimal solutions built from optimal subproblems) and overlapping subproblems (the same subproblems keep showing up), you can cache results instead of recomputing everything.

Introduction

DP comes up constantly in technical interviews—especially at Google and Amazon. Problems like edit distance between strings, optimal game strategy, and shortest path in DAGs all yield to DP. The tricky part for most people is recognizing when DP applies and how to frame the subproblems.

This guide covers memoization (top-down recursion with caching) and tabulation (bottom-up iterative filling), when to use each, and how to think about the subproblem dependency graph. I’ll walk through identifying DP subproblems, deriving recurrence relations, handling base cases, and squeezing space complexity down from O(n²) to O(1) where possible. The framework applies to Fibonacci, knapsack, LCS, edit distance, and more.

When to Use Dynamic Programming

DP fits when:

The problem breaks into overlapping subproblems
You can build optimal solutions from optimal subproblems
You’re optimizing something (minimize cost, maximize profit, etc.)

Common DP patterns:

Fibonacci numbers (the simplest overlapping subproblems)
Longest common subsequence
Edit distance
Knapsack problems
Shortest path in DAGs
String manipulation problems

Memoization (Top-Down)

Cache function results to avoid recomputation:

def fibMemo(n, memo={}):
    """Fibonacci with memoization - O(n) time, O(n) space."""
    if n in memo:
        return memo[n]
    if n <= 1:
        return n

    memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo)
    return memo[n]

Tabulation (Bottom-Up)

Build solutions from smaller subproblems upward:

def fibTab(n):
    """Fibonacci with tabulation - O(n) time, O(1) space optimized."""
    if n <= 1:
        return n

    # Only need previous two values
    prev2, prev1 = 0, 1

    for _ in range(2, n + 1):
        prev2, prev1 = prev1, prev2 + prev1

    return prev1

The DP Framework

Every DP problem follows this structure:

def solve_dp(problem_input):
    # 1. Identify the subproblem state
    #    What parameters uniquely identify a subproblem?

    # 2. Define the recurrence
    #    How does the answer for state(i) relate to state(i-1)?

    # 3. Identify base cases
    #    What are the smallest subproblems with known answers?

    # 4. Choose approach
    #    Top-down (memoization) or bottom-up (tabulation)?

    # 5. Determine order of computation
    #    For bottom-up: what order should we process states?

    pass

Identifying DP Subproblems

The hardest part is recognizing when DP applies and how to frame the state:

Problem	Subproblem State	Meaning
Fibonacci	dp[i]	ith Fibonacci number
Climbing Stairs	dp[i]	Ways to reach ith step
Coin Change	dp[i]	Min coins to make amount i
Longest Substring	dp[i][j]	LCS of substrings ending at i, j
Edit Distance	dp[i][j]	Min edits between first i and j chars

Common DP Pitfalls

Wrong subproblem definition: If states don’t uniquely identify subproblems, you get wrong answers
Missing base cases: Every recurrence needs termination conditions
Off-by-one errors: Track whether your indices are 0 or 1 based
Space optimization too early: Get correctness first, optimize later

Memoization vs Tabulation

Aspect	Memoization (Top-Down)	Tabulation (Bottom-Up)
Implementation	Recursive with cache	Iterative table filling
Order	Natural recursive order	You control order
Missing states	Automatically skipped	Must process all states
Stack overflow	Possible for deep recursion	No recursion risk
Cache locality	Poor (random access)	Good (sequential)
Best when	Subproblem graph is sparse	All subproblems needed

How to Visualize DP

DP problems click when you see the subproblem graph:

Approach	What to Watch
Memoization	Repeated calls return cached values instantly. Each revisit crosses that subproblem off the tree.
Tabulation	Table fills bottom-up. Each cell depends on cells already computed, usually the one above or to the left.
Fibonacci	One call branches into two, which branch again, until you hit the base cases at the bottom.
Knapsack	2D table fills row by row. Each cell asks: do I include this item or not?

Tracing tip: Find the smallest subproblem you can solve directly. Write that answer down, then work outward.

Quick Recap Checklist

Failure Scenarios

Scenario	Why DP Fails	Fix
Missing optimal substructure	Problem can’t be decomposed into subproblems	Rethink problem framing or try alternative approach
Incorrect state definition	States don’t uniquely identify subproblems	Add more dimensions to state if needed
Wrong base cases	Recurrence builds on incorrect foundations	Verify smallest subproblems manually
Integer overflow	Large DP values exceed language limits	Use modulo arithmetic or larger data types
Stack overflow	Deep recursion in memoization	Switch to tabulation or increase stack size

Trade-off Table

Aspect	Memoization	Tabulation
Implementation	Recursive with cache	Iterative table filling
Subproblem graph	Automatically handles sparse graphs	Must compute all states
Order of computation	Natural recursive order	Must ensure correct ordering
Stack depth risk	Yes, for deep recursion	No stack overflow possible
Cache locality	Poor (random access patterns)	Good (sequential access)
Overhead	Function call overhead	No call overhead
Best for	Sparse subproblem dependencies	Dense/complete subproblem graph
Debugging	Easier to trace recursively	May need table visualization

Interview Questions

1. What's the difference between dynamic programming and divide and conquer?

Expected answer points:

Both break problems into subproblems, but key difference is overlapping subproblems
Divide and conquer creates independent subproblems (like merge sort halves)
DP applies when same subproblems recur multiple times—cache results to avoid redundant computation
If subproblems don't overlap, DP provides no benefit

2. How do you identify if a problem requires DP?

Expected answer points:

Look for optimal substructure: optimal solution can be built from optimal subproblems
Look for overlapping subproblems: same subproblems appear multiple times
Classic hints: "minimum/maximum," "count ways to," "longest subsequence"
Problems where later decisions depend on earlier ones

3. What is space optimization in DP?

Expected answer points:

Many DP solutions use O(n) or O(n²) space but can often be reduced
If recurrence only depends on previous k states, only keep k previous values
Fibonacci example: only needs previous two values, reducing O(n) space to O(1)
Only optimize after achieving correctness—space optimization can obscure logic

4. What comes first: memoization or tabulation?

Expected answer points:

Memoization is often easier for interview problems—thinks recursively, natural subproblem structure
Tabulation is often faster and avoids recursion overhead
For problems where all subproblems will be visited, tabulation is preferred
For sparse subproblem graphs, memoization shines

5. Explain the time and space complexity trade-off in DP.

Expected answer points:

Standard DP: O(n) or O(n²) time, O(n) or O(n²) space
Space can often be reduced from O(n²) to O(n) or O(1) by keeping only relevant states
Time-space trade-off: caching costs memory but saves computation
Tabulation can improve cache locality vs memoization's potentially scattered access

6. What is the difference between top-down and bottom-up DP?

Expected answer points:

Top-down (memoization): recursive approach that starts from problem and breaks it down
Bottom-up (tabulation): iterative approach that starts from base cases and builds up
Memoization automatically skips unreachable states; tabulation must process all
Tabulation avoids stack overflow risk inherent in deep recursion

7. How do you handle DP when subproblems have multiple dependencies?

Expected answer points:

Multiple dependencies require careful ordering of computation
Build dependency graph and process in topological order
For 2D DP: ensure both i-1 and j-1 are computed before dp[i][j]
Consider which approach (memoization vs tabulation) naturally handles the dependency structure

8. What is the recurrence relation for the 0/1 knapsack problem?

Expected answer points:

dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i]) when weight[i] <= w
dp[i][w] = dp[i-1][w] when weight[i] > w (can't include item)
Base case: dp[0][w] = 0 for all w (no items)
Result is dp[n][W] where n = number of items, W = capacity

9. How would you approach a DP problem you've never seen before?

Expected answer points:

Step 1: Verify problem has optimal substructure and overlapping subproblems
Step 2: Define subproblem state—what parameters uniquely identify a subproblem
Step 3: Express solution in terms of smaller subproblems (recurrence)
Step 4: Identify base cases and choose memoization or tabulation
Step 5: Implement, test on base cases, verify correctness on examples

10. What is the edit distance problem and how does DP solve it?

Expected answer points:

Edit distance: minimum number of operations (insert, delete, substitute) to transform string A to B
dp[i][j] = minimum edits needed for first i chars of A and first j chars of B
Recurrence: if A[i] == B[j], dp[i][j] = dp[i-1][j-1]; else dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
Base cases: dp[i][0] = i (delete all), dp[0][j] = j (insert all)

11. What is the longest common subsequence (LCS) problem?

Expected answer points:

LCS finds longest subsequence present in both strings in same relative order
dp[i][j] = length of LCS of first i chars of A and first j chars of B
Recurrence: if A[i] == B[j], dp[i][j] = dp[i-1][j-1] + 1; else dp[i][j] = max(dp[i-1][j], dp[i][j-1])
Not the same as longest common substring—subsequence need not be contiguous

12. How does DP handle problems with negative values or constraints?

Expected answer points:

Negative values require careful base case handling—can't use simple min initialization
Consider whether problem asks for optimal value or just feasibility
For some problems, shift values or use offset to work in non-negative range
Unbounded knapsack can handle negative values by iterating forward in tabulation

13. What is the difference between unbounded and 0/1 knapsack?

Expected answer points:

0/1 knapsack: each item can be used at most once
Unbounded knapsack: each item can be used unlimited times
0/1: iterate weights in reverse order to prevent reusing same item
Unbounded: iterate weights in forward order to allow reusing same item

14. Can DP solve problems where optimal solution doesn't require all subproblems?

Expected answer points:

Yes—this is where memoization often outperforms tabulation
Memoization automatically computes only visited states
Tabulation requires computing all states even if only some are needed
For sparse subproblem graphs, memoization provides natural efficiency

15. How do you debug a DP solution when it's producing wrong answers?

Expected answer points:

Check subproblem definition—do parameters uniquely identify state?
Verify base cases are correct and sufficient
Check recurrence logic against problem requirements
Test on small examples and trace through by hand
Verify order of computation ensures dependencies are resolved

16. What is the House Robber problem and how does DP solve it?

Expected answer points:

House Robber: max amount you can rob without robbing adjacent houses
dp[i] = max amount robbed up to house i
Recurrence: dp[i] = max(dp[i-1], dp[i-2] + nums[i])
Space-optimized: only need previous two values, O(1) space

17. What is the rod cutting problem and how does DP approach it?

Expected answer points:

Rod cutting: max revenue from cutting rod of length n with given price table
dp[i] = max revenue obtainable for rod of length i
Recurrence: dp[i] = max(price[j] + dp[i-j]) for all j from 1 to i
Unbounded variant: same subproblem can be used multiple times in different cuts

18. How does DP apply to climbing stairs variants?

Expected answer points:

Basic: dp[i] = dp[i-1] + dp[i-2] (steps of 1 or 2)
If you can climb 1, 2, or k steps: dp[i] = dp[i-1] + dp[i-2] + ... + dp[i-k]
If forbidden step: set dp[forbidden] = 0 and continue
Space optimization: use sliding window for variable step sizes

19. What is the subset sum problem and how does DP solve it?

Expected answer points:

Subset sum: determine if subset of numbers sums to target value
dp[i] = set of achievable sums using first i elements
Or use boolean dp[i][s] = true if sum s achievable with first i elements
Recurrence: dp[i][s] = dp[i-1][s] OR dp[i-1][s-nums[i]] if nums[i] <= s

20. What is dynamic programming's relationship to graph algorithms?

Expected answer points:

Shortest path in DAG is DP: dp[v] = min(dp[u] + weight(u,v)) over incoming edges
Bellman-Ford applies DP principles across all edge relaxations
Dijkstra can be seen as DP with priority queue selection
DP on DAGs is particularly efficient: O(V+E) vs O(VE) for general graphs

Conclusion

DP works when your problem has optimal substructure and overlapping subproblems. Memoization (top-down) uses recursion with a cache and handles sparse subproblem graphs naturally. Tabulation (bottom-up) iteratively fills a table and offers better cache locality when you need all subproblems. Many O(n) or O(n²) space solutions can drop to O(1) by keeping only the previous k states the recurrence depends on.

Dynamic Programming: From Memoization to Optimal Solutions

Dynamic Programming: From Memoization to Optimal Solutions

Introduction

When to Use Dynamic Programming

Memoization (Top-Down)

Tabulation (Bottom-Up)

The DP Framework

Identifying DP Subproblems

Common DP Pitfalls

Memoization vs Tabulation

How to Visualize DP

Quick Recap Checklist

Failure Scenarios

Trade-off Table

Interview Questions

Further Reading

Conclusion

Dynamic Programming: From Memoization to Optimal Solutions

Dynamic Programming: From Memoization to Optimal Solutions

Introduction

When to Use Dynamic Programming

Memoization (Top-Down)

Tabulation (Bottom-Up)

The DP Framework

Identifying DP Subproblems

Common DP Pitfalls

Memoization vs Tabulation

How to Visualize DP

Quick Recap Checklist

Failure Scenarios

Trade-off Table

Interview Questions

Further Reading

Conclusion

Category

Tags

Related Posts

Memoization vs Tabulation: Two Faces of Dynamic Programming

1D Dynamic Programming Problems: Classic Patterns

2D Dynamic Programming: Matrix Chain and Beyond