Introduction to Dynamic Programming

This lesson defines dynamic programming (DP) as an optimization technique, explains optimal substructure and overlapping subproblems, contrasts DP with greedy and divide-and-conquer, compares memoization vs tabulation, and maps classic DP problems to real-world applications.

What is Dynamic Programming?

Dynamic programming is a method for solving complex problems by breaking them into simpler overlapping subproblems, storing the results of those subproblems, and reusing them instead of recomputing. The word dynamic refers to the table of stored answers built over time—not to runtime speed by itself.

DP is not a single algorithm like binary search; it is a problem-solving paradigm. You define a recurrence (how a larger answer depends on smaller ones), identify a state (what you must remember), and fill or cache a table of optimal values.

Schematic: Fibonacci with overlap

Naive recursion recomputes the same values many times. DP stores each fib(k) once:

fib(5)
 ├── fib(4)          fib(3)  ← fib(3) computed again without DP
 │    ├── fib(3)     fib(2)
 │    │    fib(2) fib(1)
 │    └── fib(2) fib(1)
 └── fib(3)  ← duplicate subtree

With DP: fib(0)…fib(5) stored once → O(n) time

The Two DP Properties

A problem is a strong DP candidate when both properties hold:

1. Optimal Substructure

An optimal solution to the full problem can be built from optimal solutions to its subproblems.

Example:

• Shortest path in a graph
• Best way to pack a knapsack of capacity W uses the best answers for smaller capacities
• Minimum cost to reach position i depends on minimum cost to reach i-1 and i-2

2. Overlapping Subproblems

The same subproblem appears many times in the recursion tree.

Examples:

• Fibonacci numbers
• Edit distance
• Coin change
• Longest common subsequence

DP vs Greedy vs Divide-and-Conquer

All three decompose problems, but the guarantees and storage differ:

Quick Comparison Examples

Divide & Conquer Example:

Merge Sort: [5,2,4,6,1,3]
→ Split into [5,2,4] and [6,1,3]
→ Split further until single elements
→ Merge back (no overlapping subproblems)

Greedy Example:

Coin Change (US coins): 30 cents
→ Always take largest coin: 25 + 5 = 30 ✓
→ No need to try all combinations

DP Example:

Coin Change (any coins): 30 cents with [1,3,4]
→ Need to try combinations:
   4+4+4+4+4+4+4+2 = 8 coins
   4+4+4+4+4+3+3+3+1 = 9 coins
→ Must consider all possibilities

Memoization vs Tabulation

Top-Down (Memoization)

Write the natural recursive solution, then cache results in a hash map or array when a state is first computed.

Example — Fibonacci:

def fib_memo(n, memo={}):
    if n <= 1:
        return n
    if n not in memo:
        memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]

Bottom-Up (Tabulation)

Fill a table iteratively from base cases upward, often controlling memory by keeping only the previous row or two.

Example — Fibonacci:

def fib_tab(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

Which One to Choose?

Both compute the same DP table in spirit; choose based on clarity, iteration order, and space constraints.

Where DP Shows Up

DP models optimization and counting over structured choices:

Classic DP Problems

1. Grid Problems

• Unique paths
• Minimum path sum
• Dungeon game
• Cherry pickup

2. Knapsack & Coin Problems

• 0/1 Knapsack
• Coin change (minimum coins)
• Coin change (number of ways)
• Partition equal subset sum

3. String Problems

• Longest common subsequence
• Edit distance
• Word break
• Palindrome partitioning
• Wildcard matching

4. Sequence Problems

• Longest increasing subsequence
• Maximum subarray (Kadane's algorithm)
• Decode ways

5. Stock Problems

• Best time to buy/sell stock (I, II, III, IV)
• With cooldown
• With transaction fee

6. Miscellaneous

• House robber (I, II, III)
• Jump game
• Interleaving strings
• Distinct subsequences

Real-Life Applications

Dynamic programming is not only an interview topic—it is the backbone of optimization in science, engineering, and everyday software. The table below maps classic DP families to where they appear in the real world.

Cross-Domain Examples

• Bioinformatics: Align two DNA sequences to find similarity (edit distance / LCS variants)
• Natural language processing: Word break for Chinese/Japanese; autocorrect via edit distance
• Operations research: Scheduling jobs, assigning tasks under budgets (knapsack family)
• Computer graphics: Seam carving and image segmentation use DP on grids
• Economics: Multi-period investment and consumption (stock DP models)
• Telecom: Error-correcting codes and Viterbi decoding in cell networks

Next Steps

Continue Learning

1. Memoization vs Tabulation — Deep dive into both approaches with examples
2. DP Properties & Complexity — Detailed analysis of optimal substructure and overlapping subproblems
3. Fibonacci & Climbing Stairs — Beginner problems to apply DP

Practice Problems

Beginner Level:

• Fibonacci Number
• Climbing Stairs
• Min Cost Climbing Stairs
• N-th Tribonacci Number

Intermediate Level:

• Unique Paths
• Coin Change
• House Robber
• Decode Ways

Interview Preparation

• Dynamic Programming Patterns — Recognize common DP patterns
• Code Templates — Reusable DP templates
• Common Mistakes — Avoid typical DP errors

Summary