Data Structures & AlgorithmsDynamic Programming

What Is Dynamic Programming?

LevelIntermediate

Duration60 mins

TopicDynamic Programming

4 / 4

DP vs Recursion vs Greedy

The Algorithmic Trinity

When facing an optimization problem, you have three powerful paradigms at your disposal: plain recursion (the most straightforward approach), Dynamic Programming (recursion with memory), and Greedy algorithms (local optimization without looking back).

These three approaches form a spectrum of design choices. Understanding their relationships, trade-offs, and when each applies is essential to making informed algorithmic decisions.

In this final page of our introductory module, we'll place Dynamic Programming in context—comparing it rigorously with recursion and greedy strategies. By the end, you'll have a clear mental framework for choosing the right tool for the job.

What You Will Learn

By the end of this page, you will understand the precise relationship between DP and plain recursion, how DP differs from greedy algorithms, when each approach is appropriate, and how to recognize which paradigm a problem requires.

The Relationship Between DP and Recursion

Dynamic Programming IS recursion—plus memory.

This is the most important insight about the DP-recursion relationship. DP doesn't replace recursive thinking; it enhances it. Every DP solution is built on a recursive foundation: the recurrence relation.

The evolution from recursion to DP:

Plain Recursion — Express the solution to a problem in terms of solutions to smaller subproblems. Elegant and directly mirrors the mathematical definition. BUT: may recompute the same subproblems exponentially many times.
Memoized Recursion (Top-Down DP) — Add a cache to store computed subproblems. Same recursive logic, but each subproblem is computed only once.
Tabulated Iteration (Bottom-Up DP) — Eliminate recursion entirely by computing subproblems in order. Same results, no recursive overhead.

All three produce the same final answer. The difference is purely in efficiency and implementation style.

recursion_to_dp_evolution.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
"""
Evolution from Plain Recursion to Dynamic Programming
Example: Compute nth Fibonacci number
"""
 
# Stage 1: Plain Recursion
def fib_recursive(n):
    """
    Pure recursive approach - O(2^n) time, O(n) stack space
    Directly implements the mathematical definition.
    Problem: Exponentially many redundant computations.
    """
    if n <= 1:
        return n
    return fib_recursive(n - 1) + fib_recursive(n - 2)
 
 
# Stage 2: Memoized Recursion (Top-Down DP)
def fib_memoized(n, memo={}):
    """
    Recursive with caching - O(n) time, O(n) space
    Same logic as above, but we store computed values.
    Each subproblem computed exactly once.
    """
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib_memoized(n - 1, memo) + fib_memoized(n - 2, memo)
    return memo[n]
 
 
# Stage 3: Tabulated Iteration (Bottom-Up DP)
def fib_tabulated(n):
    """
    Iterative with table - O(n) time, O(n) space
    No recursion. We fill the table from smallest to largest.
    """
    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]
 
 
# Stage 4: Space-Optimized DP
def fib_optimized(n):
    """
    Iterative with O(1) space - O(n) time, O(1) space
    We only need the last two values, so no table needed.
    """
    if n <= 1:
        return n
    prev2, prev1 = 0, 1
    for i in range(2, n + 1):
        current = prev1 + prev2
        prev2/prev1 = prev1, current
    return prev1
 
 
# All four produce the same answer, but:
# fib_recursive(40)  - takes several seconds
# fib_memoized(40)   - instant
# fib_tabulated(40)  - instant
# fib_optimized(40)  - instant (and uses least memory)

The Recursive Core

Always start by formulating the recursive solution. The recurrence relation is the heart of DP. Once you have a correct recursive formula, adding memoization or converting to iteration is mechanical. Without the correct recursive structure, no amount of optimization will help.

Recursion vs DP: Detailed Comparison
Aspect	Plain Recursion	DP (Memoization/Tabulation)
Core Logic	Recurrence relation	Same recurrence relation
Subproblem Handling	Compute every time needed	Compute once, store, reuse
Time Complexity	Often exponential	Polynomial (typically)
Space for Storage	Call stack only	Cache/table + call stack (memo) or table only (tab)
When to Use	Problems without overlapping subproblems	Problems with overlapping subproblems
Relationship	Foundation for DP thinking	Recursion + storage optimization

When Recursion Alone Suffices

Not every recursive problem needs DP. When subproblems don't overlap, plain recursion is already optimal—adding memoization would waste space without saving time.

The test for overlap:

Ask: 'Will the same subproblem be computed more than once?'

If YES → DP helps (memoization/tabulation will reduce redundancy)
If NO → Pure recursion is fine (each subproblem is visited exactly once anyway)

Classic examples without overlap: Divide and Conquer problems

Merge Sort: We split the array, sort halves independently, merge. The left half is never needed by the right half and vice versa.
Quick Sort: Partitions are independent; no partition is used twice.
Binary Search: We discard half the array each time; no discarded portion is revisited.

In these problems, the recursion tree is a proper tree (not a DAG with reconvergence), so there's no redundant computation to eliminate.

No Overlap — Recursion Suffices

•Merge Sort — halves are independent
•Quick Sort — partitions never reused
•Binary Search — discard half each step
•Tree traversals — each node visited once
•Divide and conquer on disjoint subsets

Overlap Present — DP Needed

•Fibonacci — F(n-1) and F(n-2) share subproblems
•Shortest paths — many paths share intermediate nodes
•LCS — prefixes are shared across many pairs
•Knapsack — same capacities reached via different items
•Edit distance — same prefix pairs computed repeatedly

Converting Mermaid diagram...

The Visualization Tells the Story

In Merge Sort (left), the recursion tree is a proper tree—each node is unique. In Fibonacci (right), the 'tree' is actually a DAG with nodes appearing multiple times (highlighted in red/yellow). When you see repeated subproblems in the recursion structure, that's the signal that DP will help.

The Fundamental Difference Between DP and Greedy

Both DP and Greedy are optimization paradigms. Both require optimal substructure. But they differ fundamentally in how they make decisions.

Greedy Algorithms:

Make the locally optimal choice at each step
Never reconsider — once a choice is made, it's final
Hope that local optima lead to global optimum
Fast: typically O(n) or O(n log n)
Risk: may fail (produce suboptimal solutions) for many problems

Dynamic Programming:

Consider ALL possible choices at each step
Use stored subproblem solutions to evaluate each option
Compare all alternatives and select the globally best
Slower: typically O(n²) or O(n × W)
Guarantee: always finds optimal (when applicable)

The key insight:

Greedy algorithms take a shortcut—they assume the locally best choice is globally safe. This works beautifully when the problem has the greedy choice property (local optima compose to global optima). But for problems lacking this property, greedy fails silently, producing suboptimal solutions.

DP is more thorough—it makes no assumptions. By considering all choices and comparing them using optimal subproblem solutions, DP guarantees the optimal answer at the cost of more computation.

Where Greedy Fails but DP Succeeds: Coin ChangeMake 12 cents using coins [1, 5, 6]. Minimize coins used.

Input

amount = 12, coins = [1, 5, 6]

Output

Minimum coins = 2 (using 6 + 6)

Explanation

Greedy Approach (choose largest coin first):

Choose 6 (remaining: 6) — greedy takes largest
Choose 6 (remaining: 0) — done!
Actually, greedy happens to work here. Let's try 11:

For amount = 11:

Greedy: 6 + 5 = 11 → 2 coins ✓
Optimal: Also 2 coins (6 + 5)

For amount = 9:

Greedy: 6 + 1 + 1 + 1 = 9 → 4 coins ✗
Optimal: 5 + 1 + 1 + 1 + 1 = 9 → 5 coins? No wait...
Actually: 6 + 1 + 1 + 1 = 4 coins, or 5 + 1 + 1 + 1 + 1 = 5 coins
Hmm, let me use [1, 3, 4] for amount 6:

For amount = 6 with coins [1, 3, 4]:

Greedy: 4 + 1 + 1 = 3 coins ✗
DP: 3 + 3 = 2 coins ✓

The greedy choice of 4 (the largest fitting coin) locks us into a suboptimal path. DP would consider both options (4 vs 3) and find the better one.

DP vs Greedy: Comprehensive Comparison
Property	Dynamic Programming	Greedy
Decision Strategy	Evaluate all choices, pick best	Make locally optimal choice
Backtracking	Implicitly considers all paths	Never backtracks
Optimality Guarantee	Always finds optimal	Only with greedy choice property
Required Properties	Optimal substructure + overlapping subproblems	Optimal substructure + greedy choice property
Time Complexity	Higher (polynomial, but more work)	Lower (often linear-ish)
Space Complexity	Higher (table/cache storage)	Lower (often O(1) or O(n))
Implementation Style	Recursion with memo OR iterative with table	Usually simple iteration or sorting
Proof Requirement	Recurrence correctness	Proof that greedy choice is safe

Greedy is Tempting but Dangerous

Greedy solutions are faster to write and execute. This makes them appealing. But greedy only works when provably correct. Applying greedy without verification often leads to wrong answers that look plausible. When in doubt, use DP—it's slower but safe.

When Greedy Is Correct

Greedy algorithms work when the problem has the Greedy Choice Property: making the locally optimal choice at each step leads to a globally optimal solution.

Mathematical Statement:

A problem has the greedy choice property if there exists some optimal solution that makes the greedy choice. In other words, we can always safely make the locally best choice without foreclosing the possibility of reaching a global optimum.

Classic problems where greedy works:

Greedy-Solvable Problems

•Activity Selection — Choose the activity with the earliest finish time. This maximizes remaining time for future activities.
•Fractional Knapsack — Take items by best value-per-weight ratio. When fractions are allowed, this greedily optimal.
•Huffman Coding — Combine the two least-frequent symbols first. This minimizes weighted path length.
•Minimum Spanning Tree (Kruskal/Prim) — Always add the minimum-weight edge that doesn't form a cycle. The cut property guarantees this is safe.
•Dijkstra's Algorithm — Extend the shortest known path. Works when all edge weights are non-negative.
•Coin Change (with canonical coin systems) — Greedy works for US coins (1, 5, 10, 25) but NOT for arbitrary coin systems.

greedy_example.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
"""
Activity Selection Problem - Classic Greedy
 
Problem: Given n activities with start and finish times,
select the maximum number of non-overlapping activities.
 
Greedy Strategy: Always pick the activity with the earliest finish time
among activities compatible with already selected ones.
 
Why it works: Earlier finish time means more room for future activities.
This is provably optimal via exchange argument.
"""
 
def activity_selection(activities):
    """
    activities: list of (start, finish) tuples
    Returns: list of selected activities (indices)
    
    Time: O(n log n) for sorting, O(n) for selection
    """
    # Sort by finish time (greedy criterion)
    sorted_activities = sorted(enumerate(activities), key=lambda x: x[1][1])
    
    selected = []
    last_finish = 0
    
    for idx, (start, finish) in sorted_activities:
        if start >= last_finish:  # Compatible with previous selection
            selected.append(idx)
            last_finish = finish
    
    return selected
 
# Example
activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11)]
# Greedy selects activities finishing at 4, 7, 11 → 3 activities
# This is provably optimal
 
result = activity_selection(activities)
print(f"Selected activities: {result}")  # [0, 3, 7] or similar
 
 
"""
Contrast: Coin Change - Greedy FAILS for arbitrary coin systems
"""
 
def coin_change_greedy(amount, coins):
    """
    Greedy coin change: always use the largest coin that fits.
    WARNING: Only optimal for certain coin systems (like US coins).
    """
    coins_sorted = sorted(coins, reverse=True)
    count = 0
    remaining = amount
    
    for coin in coins_sorted:
        while remaining >= coin:
            remaining -= coin
            count += 1
    
    return count if remaining == 0 else -1
 
# Works for US coins:
# coin_change_greedy(87, [25, 10, 5, 1]) = 6 (3*25 + 1*10 + 0*5 + 2*1) ✓
 
# Fails for arbitrary coins:
# coin_change_greedy(6, [4, 3, 1]) = 3 (4+1+1) ✗
# Optimal: 2 (3+3)

Proving Greedy Correctness

To prove greedy works, use the 'exchange argument': assume an optimal solution that doesn't make the greedy choice, and show you can swap in the greedy choice without worsening the solution. This proves the greedy choice is always safe.

When DP Is Necessary

DP is necessary when:

The problem has optimal substructure — The optimal solution can be constructed from optimal solutions to subproblems.
The problem has overlapping subproblems — The same subproblems are needed multiple times.
Greedy doesn't work — There's no safe local choice that guarantees global optimality.

Classic problems requiring DP:

Problems Requiring Dynamic Programming
Problem	Why Greedy Fails	DP Approach
0/1 Knapsack	Can't take fractions; best ratio item may not fit optimally	Consider take/not-take for each item
Longest Common Subsequence	No local criterion for matching vs skipping characters	Try all match/skip combinations via recurrence
Edit Distance	No greedy rule for insert/delete/replace sequence	Consider all operations at each position
Matrix Chain Multiplication	No obvious way to choose split points	Try all split points, pick minimum
Coin Change (general)	Largest coin may lead to suboptimal path	Try all coins at each step, pick minimum
Subset Sum	Can't greedily include/exclude items	Consider include/exclude for each item
Palindrome Partitioning	No local criterion for cut positions	Try all cut positions, pick minimum

The common thread:

In each of these problems, you must consider multiple choices at each step, and the correct choice depends on the global context—not just local information. DP handles this by exhaustively exploring all choices and using stored subproblem solutions to efficiently evaluate each.

Warning signs that greedy won't work:

The problem involves making choices with long-term consequences
Local optimization doesn't account for constraints that appear later
Counterexamples are easy to construct where greedy fails
The problem has a 'combinatorial' feel (combinations, subsets, permutations)

DP as the Safe Default

When facing an optimization problem, try to find a greedy solution first—it's faster. But if you can't prove greedy correctness (or can find a counterexample), switch to DP. DP is the safe fallback that always finds the optimal solution when it's applicable.

A Unified View — The Algorithm Selection Framework

Here's a practical framework for choosing among recursion, DP, and greedy when facing an optimization problem:

Step 1: Identify the problem type

Is it an optimization problem (min/max/count)?
What are the constraints?
What is the decision structure?

Step 2: Check for optimal substructure

Can the optimal solution be built from optimal solutions to subproblems?
Can you express the answer recursively?

If NO → Problem may require different approach (e.g., exhaustive search, mathematical formula)

Step 3: Check for greedy choice property

Is there a local choice that's always safe?
Can you prove it (exchange argument)?
Can you find a counterexample?

If YES (provable) → Use Greedy If UNSURE → Continue to Step 4

Step 4: Check for overlapping subproblems

Will the same subproblem be computed multiple times in naive recursion?
How many distinct subproblems exist?

If YES (polynomial overlap) → Use DP If NO → Use Plain Recursion (Divide and Conquer)

Converting Mermaid diagram...

Decision criteria summary:

Condition	Strategy
Optimal substructure + Greedy choice property	Greedy (fastest when correct)
Optimal substructure + Overlapping subproblems + No greedy property	DP (guaranteed optimal)
Optimal substructure + No overlap	Divide & Conquer (plain recursion)
No optimal substructure	Problem-specific approach

The pragmatic approach:

Try greedy first (quick to implement, fast to run)
Test thoroughly—look for counterexamples
If greedy fails, formulate recursive solution
Add memoization to get DP
Optimize to tabulation if needed for space/speed

Practical Examples — All Three Approaches

Let's see all three approaches applied to related problems to reinforce the distinctions:

Example 1: Maximum Sum Subarray

max_subarray_greedy.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def max_subarray_kadane(nums):
    """
    Kadane's Algorithm - Greedy approach.
    
    The greedy choice: at each position, decide whether to
    extend the current subarray or start fresh.
    
    This works because the locally optimal choice
    (extend if positive sum, restart otherwise)
    leads to global optimum.
    """
    max_sum = current_sum = nums[0]
    
    for num in nums[1:]:
        # Greedy choice: extend or restart
        current_sum = max(num, current_sum + num)
        max_sum = max(max_sum, current_sum)
    
    return max_sum
 
# Why greedy works here:
# If current_sum < 0, extending would only hurt us.
# So we greedily restart. This is provably optimal.

Example 2: Coin Change — Where Greedy Fails

coin_greedy.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def coin_change_greedy(amount, coins):
    """
    Greedy coin change - INCORRECT for general coin systems!
    """
    coins = sorted(coins, reverse=True)
    count = 0
    
    for coin in coins:
        while amount >= coin:
            amount -= coin
            count += 1
    
    return count if amount == 0 else -1
 
# Test: amount=6, coins=[4, 3, 1]
# Greedy: 4+1+1 = 3 coins  ✗ WRONG
# Optimal: 3+3 = 2 coins   ✓

When Greedy = DP

Sometimes the "best" DP solution simplifies to greedy. Maximum subarray (Kadane's) is an example—the DP recurrence has such simple structure that it's effectively greedy. This happens when there's only one "good" choice at each step, making exhaustive comparison unnecessary.

Summary: DP vs Recursion vs Greedy

We've completed our exploration of how Dynamic Programming relates to plain recursion and greedy algorithms. Let's consolidate the key insights:

Key Takeaways

•DP is recursion with memory — The recurrence relation is the same; DP adds caching to avoid redundant computation.
•Plain recursion suffices without overlap — Divide-and-conquer problems (merge sort, binary search) don't need DP.
•Greedy is faster but riskier — Use greedy when you can prove the greedy choice property; otherwise, it may fail.
•DP is the safe fallback — When greedy can't be proven correct, DP guarantees optimality.
•Use the selection framework — Check for optimal substructure, then greedy choice property, then overlap.
•Sometimes greedy = DP — When the optimal DP transition is always the same choice, DP simplifies to greedy.

The Complete Picture
Paradigm	When to Use	Guarantee	Typical Complexity
Plain Recursion	No overlapping subproblems (D&C)	Correct if recurrence is correct	Depends on problem
Dynamic Programming	Optimal substructure + overlapping subproblems	Optimal solution guaranteed	Polynomial
Greedy	Optimal substructure + greedy choice property	Optimal only if property holds	Often O(n) or O(n log n)

Module Complete! 🎉

Congratulations! You've completed the foundational module on Dynamic Programming. You now understand what DP is (an optimization technique), how it works (breaking into subproblems with storage), and how it relates to recursion and greedy algorithms. In the next module, we'll dive deeper into overlapping subproblems—the key property that makes DP efficient.

Coming up next:

Module 2 explores Overlapping Subproblems in depth—what makes subproblems 'overlapping', how to identify overlap, and why this property is the key to DP's efficiency gains. We'll analyze the structure of recursion trees and see exactly where the exponential savings come from.

4 / 4

Loading learning content...

Data Structures & AlgorithmsDynamic Programming

What Is Dynamic Programming?

LevelIntermediate

Duration60 mins

TopicDynamic Programming

4 / 4

DP vs Recursion vs Greedy

The Algorithmic Trinity

These three approaches form a spectrum of design choices. Understanding their relationships, trade-offs, and when each applies is essential to making informed algorithmic decisions.

What You Will Learn

The Relationship Between DP and Recursion

Dynamic Programming IS recursion—plus memory.

The evolution from recursion to DP:

Plain Recursion — Express the solution to a problem in terms of solutions to smaller subproblems. Elegant and directly mirrors the mathematical definition. BUT: may recompute the same subproblems exponentially many times.
Memoized Recursion (Top-Down DP) — Add a cache to store computed subproblems. Same recursive logic, but each subproblem is computed only once.
Tabulated Iteration (Bottom-Up DP) — Eliminate recursion entirely by computing subproblems in order. Same results, no recursive overhead.

All three produce the same final answer. The difference is purely in efficiency and implementation style.

recursion_to_dp_evolution.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
"""
Evolution from Plain Recursion to Dynamic Programming
Example: Compute nth Fibonacci number
"""
 
# Stage 1: Plain Recursion
def fib_recursive(n):
    """
    Pure recursive approach - O(2^n) time, O(n) stack space
    Directly implements the mathematical definition.
    Problem: Exponentially many redundant computations.
    """
    if n <= 1:
        return n
    return fib_recursive(n - 1) + fib_recursive(n - 2)
 
 
# Stage 2: Memoized Recursion (Top-Down DP)
def fib_memoized(n, memo={}):
    """
    Recursive with caching - O(n) time, O(n) space
    Same logic as above, but we store computed values.
    Each subproblem computed exactly once.
    """
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib_memoized(n - 1, memo) + fib_memoized(n - 2, memo)
    return memo[n]
 
 
# Stage 3: Tabulated Iteration (Bottom-Up DP)
def fib_tabulated(n):
    """
    Iterative with table - O(n) time, O(n) space
    No recursion. We fill the table from smallest to largest.
    """
    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]
 
 
# Stage 4: Space-Optimized DP
def fib_optimized(n):
    """
    Iterative with O(1) space - O(n) time, O(1) space
    We only need the last two values, so no table needed.
    """
    if n <= 1:
        return n
    prev2, prev1 = 0, 1
    for i in range(2, n + 1):
        current = prev1 + prev2
        prev2/prev1 = prev1, current
    return prev1
 
 
# All four produce the same answer, but:
# fib_recursive(40)  - takes several seconds
# fib_memoized(40)   - instant
# fib_tabulated(40)  - instant
# fib_optimized(40)  - instant (and uses least memory)

The Recursive Core

Recursion vs DP: Detailed Comparison
Aspect	Plain Recursion	DP (Memoization/Tabulation)
Core Logic	Recurrence relation	Same recurrence relation
Subproblem Handling	Compute every time needed	Compute once, store, reuse
Time Complexity	Often exponential	Polynomial (typically)
Space for Storage	Call stack only	Cache/table + call stack (memo) or table only (tab)
When to Use	Problems without overlapping subproblems	Problems with overlapping subproblems
Relationship	Foundation for DP thinking	Recursion + storage optimization

When Recursion Alone Suffices

Not every recursive problem needs DP. When subproblems don't overlap, plain recursion is already optimal—adding memoization would waste space without saving time.

The test for overlap:

Ask: 'Will the same subproblem be computed more than once?'

If YES → DP helps (memoization/tabulation will reduce redundancy)
If NO → Pure recursion is fine (each subproblem is visited exactly once anyway)

Classic examples without overlap: Divide and Conquer problems

Merge Sort: We split the array, sort halves independently, merge. The left half is never needed by the right half and vice versa.
Quick Sort: Partitions are independent; no partition is used twice.
Binary Search: We discard half the array each time; no discarded portion is revisited.

In these problems, the recursion tree is a proper tree (not a DAG with reconvergence), so there's no redundant computation to eliminate.

No Overlap — Recursion Suffices

•Merge Sort — halves are independent
•Quick Sort — partitions never reused
•Binary Search — discard half each step
•Tree traversals — each node visited once
•Divide and conquer on disjoint subsets

Overlap Present — DP Needed

•Fibonacci — F(n-1) and F(n-2) share subproblems
•Shortest paths — many paths share intermediate nodes
•LCS — prefixes are shared across many pairs
•Knapsack — same capacities reached via different items
•Edit distance — same prefix pairs computed repeatedly

Converting Mermaid diagram...

The Visualization Tells the Story

The Fundamental Difference Between DP and Greedy

Both DP and Greedy are optimization paradigms. Both require optimal substructure. But they differ fundamentally in how they make decisions.

Greedy Algorithms:

Make the locally optimal choice at each step
Never reconsider — once a choice is made, it's final
Hope that local optima lead to global optimum
Fast: typically O(n) or O(n log n)
Risk: may fail (produce suboptimal solutions) for many problems

Dynamic Programming:

Consider ALL possible choices at each step
Use stored subproblem solutions to evaluate each option
Compare all alternatives and select the globally best
Slower: typically O(n²) or O(n × W)
Guarantee: always finds optimal (when applicable)

The key insight:

DP is more thorough—it makes no assumptions. By considering all choices and comparing them using optimal subproblem solutions, DP guarantees the optimal answer at the cost of more computation.

Where Greedy Fails but DP Succeeds: Coin ChangeMake 12 cents using coins [1, 5, 6]. Minimize coins used.

Input

amount = 12, coins = [1, 5, 6]

Output

Minimum coins = 2 (using 6 + 6)

Explanation

Greedy Approach (choose largest coin first):

Choose 6 (remaining: 6) — greedy takes largest
Choose 6 (remaining: 0) — done!
Actually, greedy happens to work here. Let's try 11:

For amount = 11:

Greedy: 6 + 5 = 11 → 2 coins ✓
Optimal: Also 2 coins (6 + 5)

For amount = 9:

Greedy: 6 + 1 + 1 + 1 = 9 → 4 coins ✗
Optimal: 5 + 1 + 1 + 1 + 1 = 9 → 5 coins? No wait...
Actually: 6 + 1 + 1 + 1 = 4 coins, or 5 + 1 + 1 + 1 + 1 = 5 coins
Hmm, let me use [1, 3, 4] for amount 6:

For amount = 6 with coins [1, 3, 4]:

Greedy: 4 + 1 + 1 = 3 coins ✗
DP: 3 + 3 = 2 coins ✓

The greedy choice of 4 (the largest fitting coin) locks us into a suboptimal path. DP would consider both options (4 vs 3) and find the better one.

DP vs Greedy: Comprehensive Comparison
Property	Dynamic Programming	Greedy
Decision Strategy	Evaluate all choices, pick best	Make locally optimal choice
Backtracking	Implicitly considers all paths	Never backtracks
Optimality Guarantee	Always finds optimal	Only with greedy choice property
Required Properties	Optimal substructure + overlapping subproblems	Optimal substructure + greedy choice property
Time Complexity	Higher (polynomial, but more work)	Lower (often linear-ish)
Space Complexity	Higher (table/cache storage)	Lower (often O(1) or O(n))
Implementation Style	Recursion with memo OR iterative with table	Usually simple iteration or sorting
Proof Requirement	Recurrence correctness	Proof that greedy choice is safe

Greedy is Tempting but Dangerous

When Greedy Is Correct

Greedy algorithms work when the problem has the Greedy Choice Property: making the locally optimal choice at each step leads to a globally optimal solution.

Mathematical Statement:

Classic problems where greedy works:

Greedy-Solvable Problems

•Activity Selection — Choose the activity with the earliest finish time. This maximizes remaining time for future activities.
•Fractional Knapsack — Take items by best value-per-weight ratio. When fractions are allowed, this greedily optimal.
•Huffman Coding — Combine the two least-frequent symbols first. This minimizes weighted path length.
•Minimum Spanning Tree (Kruskal/Prim) — Always add the minimum-weight edge that doesn't form a cycle. The cut property guarantees this is safe.
•Dijkstra's Algorithm — Extend the shortest known path. Works when all edge weights are non-negative.
•Coin Change (with canonical coin systems) — Greedy works for US coins (1, 5, 10, 25) but NOT for arbitrary coin systems.

greedy_example.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
"""
Activity Selection Problem - Classic Greedy
 
Problem: Given n activities with start and finish times,
select the maximum number of non-overlapping activities.
 
Greedy Strategy: Always pick the activity with the earliest finish time
among activities compatible with already selected ones.
 
Why it works: Earlier finish time means more room for future activities.
This is provably optimal via exchange argument.
"""
 
def activity_selection(activities):
    """
    activities: list of (start, finish) tuples
    Returns: list of selected activities (indices)
    
    Time: O(n log n) for sorting, O(n) for selection
    """
    # Sort by finish time (greedy criterion)
    sorted_activities = sorted(enumerate(activities), key=lambda x: x[1][1])
    
    selected = []
    last_finish = 0
    
    for idx, (start, finish) in sorted_activities:
        if start >= last_finish:  # Compatible with previous selection
            selected.append(idx)
            last_finish = finish
    
    return selected
 
# Example
activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11)]
# Greedy selects activities finishing at 4, 7, 11 → 3 activities
# This is provably optimal
 
result = activity_selection(activities)
print(f"Selected activities: {result}")  # [0, 3, 7] or similar
 
 
"""
Contrast: Coin Change - Greedy FAILS for arbitrary coin systems
"""
 
def coin_change_greedy(amount, coins):
    """
    Greedy coin change: always use the largest coin that fits.
    WARNING: Only optimal for certain coin systems (like US coins).
    """
    coins_sorted = sorted(coins, reverse=True)
    count = 0
    remaining = amount
    
    for coin in coins_sorted:
        while remaining >= coin:
            remaining -= coin
            count += 1
    
    return count if remaining == 0 else -1
 
# Works for US coins:
# coin_change_greedy(87, [25, 10, 5, 1]) = 6 (3*25 + 1*10 + 0*5 + 2*1) ✓
 
# Fails for arbitrary coins:
# coin_change_greedy(6, [4, 3, 1]) = 3 (4+1+1) ✗
# Optimal: 2 (3+3)

Proving Greedy Correctness

When DP Is Necessary

DP is necessary when:

The problem has optimal substructure — The optimal solution can be constructed from optimal solutions to subproblems.
The problem has overlapping subproblems — The same subproblems are needed multiple times.
Greedy doesn't work — There's no safe local choice that guarantees global optimality.

Classic problems requiring DP:

Problems Requiring Dynamic Programming
Problem	Why Greedy Fails	DP Approach
0/1 Knapsack	Can't take fractions; best ratio item may not fit optimally	Consider take/not-take for each item
Longest Common Subsequence	No local criterion for matching vs skipping characters	Try all match/skip combinations via recurrence
Edit Distance	No greedy rule for insert/delete/replace sequence	Consider all operations at each position
Matrix Chain Multiplication	No obvious way to choose split points	Try all split points, pick minimum
Coin Change (general)	Largest coin may lead to suboptimal path	Try all coins at each step, pick minimum
Subset Sum	Can't greedily include/exclude items	Consider include/exclude for each item
Palindrome Partitioning	No local criterion for cut positions	Try all cut positions, pick minimum

The common thread:

Warning signs that greedy won't work:

The problem involves making choices with long-term consequences
Local optimization doesn't account for constraints that appear later
Counterexamples are easy to construct where greedy fails
The problem has a 'combinatorial' feel (combinations, subsets, permutations)

DP as the Safe Default

A Unified View — The Algorithm Selection Framework

Here's a practical framework for choosing among recursion, DP, and greedy when facing an optimization problem:

Step 1: Identify the problem type

Is it an optimization problem (min/max/count)?
What are the constraints?
What is the decision structure?

Step 2: Check for optimal substructure

Can the optimal solution be built from optimal solutions to subproblems?
Can you express the answer recursively?

If NO → Problem may require different approach (e.g., exhaustive search, mathematical formula)

Step 3: Check for greedy choice property

Is there a local choice that's always safe?
Can you prove it (exchange argument)?
Can you find a counterexample?

If YES (provable) → Use Greedy If UNSURE → Continue to Step 4

Step 4: Check for overlapping subproblems

Will the same subproblem be computed multiple times in naive recursion?
How many distinct subproblems exist?

If YES (polynomial overlap) → Use DP If NO → Use Plain Recursion (Divide and Conquer)

Converting Mermaid diagram...

Decision criteria summary:

Condition	Strategy
Optimal substructure + Greedy choice property	Greedy (fastest when correct)
Optimal substructure + Overlapping subproblems + No greedy property	DP (guaranteed optimal)
Optimal substructure + No overlap	Divide & Conquer (plain recursion)
No optimal substructure	Problem-specific approach

The pragmatic approach:

Try greedy first (quick to implement, fast to run)
Test thoroughly—look for counterexamples
If greedy fails, formulate recursive solution
Add memoization to get DP
Optimize to tabulation if needed for space/speed

Practical Examples — All Three Approaches

Let's see all three approaches applied to related problems to reinforce the distinctions:

Example 1: Maximum Sum Subarray

max_subarray_greedy.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def max_subarray_kadane(nums):
    """
    Kadane's Algorithm - Greedy approach.
    
    The greedy choice: at each position, decide whether to
    extend the current subarray or start fresh.
    
    This works because the locally optimal choice
    (extend if positive sum, restart otherwise)
    leads to global optimum.
    """
    max_sum = current_sum = nums[0]
    
    for num in nums[1:]:
        # Greedy choice: extend or restart
        current_sum = max(num, current_sum + num)
        max_sum = max(max_sum, current_sum)
    
    return max_sum
 
# Why greedy works here:
# If current_sum < 0, extending would only hurt us.
# So we greedily restart. This is provably optimal.

Example 2: Coin Change — Where Greedy Fails

coin_greedy.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def coin_change_greedy(amount, coins):
    """
    Greedy coin change - INCORRECT for general coin systems!
    """
    coins = sorted(coins, reverse=True)
    count = 0
    
    for coin in coins:
        while amount >= coin:
            amount -= coin
            count += 1
    
    return count if amount == 0 else -1
 
# Test: amount=6, coins=[4, 3, 1]
# Greedy: 4+1+1 = 3 coins  ✗ WRONG
# Optimal: 3+3 = 2 coins   ✓

When Greedy = DP

Summary: DP vs Recursion vs Greedy

We've completed our exploration of how Dynamic Programming relates to plain recursion and greedy algorithms. Let's consolidate the key insights:

Key Takeaways

•DP is recursion with memory — The recurrence relation is the same; DP adds caching to avoid redundant computation.
•Plain recursion suffices without overlap — Divide-and-conquer problems (merge sort, binary search) don't need DP.
•Greedy is faster but riskier — Use greedy when you can prove the greedy choice property; otherwise, it may fail.
•DP is the safe fallback — When greedy can't be proven correct, DP guarantees optimality.
•Use the selection framework — Check for optimal substructure, then greedy choice property, then overlap.
•Sometimes greedy = DP — When the optimal DP transition is always the same choice, DP simplifies to greedy.

The Complete Picture
Paradigm	When to Use	Guarantee	Typical Complexity
Plain Recursion	No overlapping subproblems (D&C)	Correct if recurrence is correct	Depends on problem
Dynamic Programming	Optimal substructure + overlapping subproblems	Optimal solution guaranteed	Polynomial
Greedy	Optimal substructure + greedy choice property	Optimal only if property holds	Often O(n) or O(n log n)

Module Complete! 🎉

Coming up next:

4 / 4