Data Structures & AlgorithmsDynamic Programming

Optimal Substructure — The Foundation of Dynamic Programming

LevelIntermediate

Duration60 mins

TopicDynamic Programming

3 / 4

Connection to Greedy Optimal Substructure

Two Paradigms, One Property: The Optimal Substructure Connection

Here's a striking fact: both dynamic programming and greedy algorithms rely on optimal substructure. This isn't coincidence—it's fundamental to how both paradigms work. Yet despite sharing this core property, they produce dramatically different algorithms.

Dynamic programming explores all choices and combines optimal subsolutions. Greedy algorithms commit to one choice immediately with no backtracking. Both require optimal substructure, but greedy demands something more: the greedy choice property.

Understanding this connection is crucial because it answers a practical question every algorithm designer faces: Given a problem with optimal substructure, should I use DP or greedy? The answer unlocks significant efficiency gains when greedy works, and prevents failed attempts when it doesn't.

What You Will Master

By the end of this page, you will understand: how optimal substructure manifests in greedy algorithms, the additional property (greedy choice) that distinguishes greedy from DP, why greedy is 'DP without exploring all choices', and how to determine which paradigm fits a given problem.

Optimal Substructure: The Common Foundation

Let's establish clearly how both paradigms use optimal substructure.

In Dynamic Programming:

We decompose a problem into subproblems, solve each subproblem optimally, and combine the optimal subsolutions. The recurrence relation expresses this:

OPT(problem) = best_over_all_choices { cost(choice) + OPT(subproblem_after_choice) }

We must explore all choices because we don't know which leads to the global optimum. Optimal substructure guarantees that once we've found the best choice, its corresponding subproblem solution is also optimal.

In Greedy Algorithms:

We also decompose into subproblems. But instead of exploring all choices, we immediately commit to the locally best choice:

OPT(problem) = greedy_choice + OPT(subproblem_after_greedy_choice)

We don't explore alternatives because the greedy choice property guarantees that the locally best choice is part of some global optimum. Optimal substructure then ensures the remaining subproblem can be solved optimally.

Optimal Substructure Usage Comparison
Aspect	Dynamic Programming	Greedy Algorithm
Uses optimal substructure?	Yes (essential)	Yes (essential)
How subproblems are solved	All explored, best kept	Only one path explored
Choice exploration	Try all valid choices	Commit to best local choice
Guarantees optimality via	Exhaustive comparison	Greedy choice property + optimal substructure
Backtracking?	Implicit (via exploring all)	Never
Typical complexity	Polynomial (with memoization)	Often O(n log n) or O(n)

The Key Difference

Both paradigms share optimal substructure. The difference is how many choices they explore. DP explores all choices because it must compare them. Greedy explores only one because the greedy choice property promises that choice is safe. Same foundation, different superstructures.

The Greedy Choice Property: What Greedy Adds

Greedy algorithms work only when optimal substructure is paired with the greedy choice property:

A globally optimal solution can be obtained by making locally optimal (greedy) choices.

More precisely: at each step, there exists a locally optimal choice that is consistent with at least one globally optimal solution. Making this choice never forecloses the possibility of reaching a global optimum.

Formal statement:

Let c be the greedy choice at the current state. Then there exists some optimal solution S* such that c ∈ S* (c is part of S*). Therefore, making choice c still allows us to reach an optimal solution.

Why this is powerful:

If the greedy choice property holds, we never need to explore alternatives. The locally best choice is always safe—it leads to some optimal solution. We can commit immediately and recursively solve the remaining subproblem (using optimal substructure).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
WITHOUT Greedy Choice Property (need DP):
═══════════════════════════════════════
                    ┌─────── Choice A → leads to optimal path
State → explore → ├─────── Choice B → leads to suboptimal path  
                    └─────── Choice C → leads to optimal path
 
We don't know which choice leads to optimum without exploring all.
DP explores all, compares, picks best.
 
 
WITH Greedy Choice Property (can use Greedy):
═══════════════════════════════════════
                    ┌─────── Choice A (locally best) → guaranteed to be in SOME optimal
State → choose → ──┤
                    └─────── Other choices → might also be optimal, but A is sufficient
 
We KNOW the locally best choice is "safe" — no need to explore others.
Greedy commits to A immediately.
 
 
The Guarantee:
If "locally best" → "part of some optimal solution",
then we never need backtracking.
Make greedy choice → solve remaining subproblem optimally → done.

Requirements for Greedy to Work

•Optimal substructure: The problem breaks into subproblems, and optimal solutions contain optimal subsolutions.
•Greedy choice property: A locally optimal choice is always part of some globally optimal solution.
•No 'traps': Making the greedy choice never leads us to a state from which no optimal solution is reachable.

Optimal Substructure Alone Is Not Enough for Greedy

Many problems have optimal substructure but NOT the greedy choice property. For these, greedy fails and DP is required. The 0/1 knapsack is the classic example: it has optimal substructure (DP works), but the locally best item isn't always globally best (greedy fails).

Case Study: Activity Selection (Greedy Works)

Let's examine a problem where greedy succeeds, and trace exactly how both optimal substructure and the greedy choice property enable it.

Problem: Activity Selection

Given n activities with start and finish times, select the maximum number of non-overlapping activities.

The greedy approach:

Sort activities by finish time
Always select the activity that finishes earliest (among compatible ones)
Repeat until no compatible activities remain

Why it works:

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
// Activity Selection: Greedy works because of BOTH properties
 
interface Activity {
    start: number;
    finish: number;
}
 
function maxActivities(activities: Activity[]): Activity[] {
    // Sort by finish time (enables greedy choice)
    activities.sort((a, b) => a.finish - b.finish);
    
    const selected: Activity[] = [];
    let lastFinish = -Infinity;
    
    for (const activity of activities) {
        if (activity.start >= lastFinish) {
            // GREEDY CHOICE: Select the next compatible activity
            // that finishes earliest
            selected.push(activity);
            lastFinish = activity.finish;
        }
    }
    
    return selected;
}
 
// ═══════════════════════════════════════════════════════════
// WHY GREEDY WORKS: PROOF SKETCH
// ═══════════════════════════════════════════════════════════
 
// PROPERTY 1: Greedy Choice Property
// 
// Claim: The activity that finishes first is part of SOME optimal solution.
// 
// Proof: Let A1 be the activity finishing first. Let OPT be any optimal solution.
// 
// Case 1: A1 ∈ OPT. Already part of optimum, done.
// 
// Case 2: A1 ∉ OPT. Let Aj be the first activity in OPT.
//   Since A1 finishes first overall, A1.finish ≤ Aj.finish.
//   So A1 is compatible with all activities that Aj is compatible with.
//   EXCHANGE: Replace Aj with A1 in OPT.
//   This is still valid (A1 ends earlier, so no new conflicts).
//   This is still optimal (same number of activities).
//   Now A1 is in an optimal solution. ∎
 
// PROPERTY 2: Optimal Substructure
// 
// After selecting the earliest-finishing activity A1:
// Remaining problem: select max activities from those starting after A1.finish.
// 
// Claim: Optimal solution = {A1} ∪ OPT(remaining activities).
// 
// Proof: If OPT(remaining) weren't optimal for the remaining activities,
// we could improve it, improving the overall count.
// This contradicts that we have an optimal overall solution.
// So OPT(remaining) MUST be optimal. ∎
 
// Together: Greedy choice is safe + remaining is solved optimally = optimal!

The interplay of both properties:

Greedy choice property tells us: selecting the earliest-finishing activity is safe—it's part of some optimal solution.
Optimal substructure tells us: once we've made that choice, the remaining problem is a smaller instance of the same problem, and we should solve it optimally.
Greedy recursion: We apply the greedy choice repeatedly, each time reducing to a smaller subproblem, confident that local + optimal-remaining = global optimal.

Without both properties, this wouldn't work. Without greedy choice property, earliest-finishing might not be safe. Without optimal substructure, optimal-remaining might not combine into optimal-whole.

Case Study: 0/1 Knapsack (Greedy Fails, DP Works)

Now let's examine a problem where greedy fails despite optimal substructure being present.

Problem: 0/1 Knapsack

Given n items, each with weight wᵢ and value vᵢ, and a knapsack with capacity W, select items to maximize total value without exceeding capacity. Each item is either fully taken (1) or not taken (0).

Does it have optimal substructure? Yes!

If the optimal solution includes item n, then the remaining items must form an optimal solution for the subproblem with capacity W - wₙ. If the optimal solution excludes item n, then the remaining items must form an optimal solution for capacity W.

Why doesn't greedy work?

The natural greedy strategies fail:

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
69
70
// 0/1 Knapsack: Optimal substructure ✓, Greedy choice property ✗
 
// GREEDY ATTEMPT 1: Take highest value items first
// 
// Counterexample:
// Capacity = 10
// Items: A(weight=6, value=30), B(weight=5, value=25), C(weight=5, value=24)
// 
// Greedy by value: Take A (value 30, weight 6). Remaining capacity: 4.
// No other item fits. Total: 30.
// 
// Optimal: Take B + C (value 25+24=49, weight 10). Total: 49.
// 
// Greedy by value is WRONG. ✗
 
// GREEDY ATTEMPT 2: Take by value-to-weight ratio
// 
// Counterexample:
// Capacity = 10
// Items: A(w=1, v=6, ratio=6), B(w=10, v=50, ratio=5)
// 
// Greedy by ratio: Take A (ratio 6). Remaining capacity: 9.
// B doesn't fit. Total: 6.
// 
// Optimal: Take B alone. Total: 50.
// 
// Greedy by ratio is WRONG. ✗
 
// GREEDY ATTEMPT 3: Take smallest weight items first
//
// Counterexample:
// Capacity = 10
// Items: A(w=1, v=1), B(w=9, v=100)
//
// Greedy by weight: Take A. Remaining capacity: 9.
// Take B. Total: 101. (Happens to work here, but...)
//
// Different example:
// Items: A(w=1, v=1), B(w=1, v=1), C(w=1, v=1), ..., ten items of (w=1, v=1)
// Plus: D(w=10, v=50)
//
// Greedy by weight: Take all small items. Total: 10.
// Optimal: Take D. Total: 50.
//
// Greedy by weight is WRONG. ✗
 
// CONCLUSION:
// No greedy strategy works for 0/1 knapsack.
// We MUST use DP to find the optimal solution.
 
function knapsackDP(weights: number[], values: number[], capacity: number): number {
    const n = weights.length;
    const dp = Array.from({length: n + 1}, () => Array(capacity + 1).fill(0));
    
    for (let i = 1; i <= n; i++) {
        for (let w = 0; w <= capacity; w++) {
            // Optimal substructure is used here:
            // We trust dp[i-1][...] to be optimal for those subproblems
            dp[i][w] = dp[i - 1][w];  // Exclude item i
            if (weights[i - 1] <= w) {
                dp[i][w] = Math.max(
                    dp[i][w], 
                    values[i - 1] + dp[i - 1][w - weights[i - 1]]  // Include item i
                );
            }
        }
    }
    
    return dp[n][capacity];
}

Why greedy choice property fails:

The core issue is that the locally best choice isn't always globally safe. Consider items sorted by value-to-weight ratio:

The item with best ratio might use capacity needed for a combination of items that together provide more value.
Making the greedy choice can foreclose better options.
There's no exchange argument that works: swapping a greedy item for the optimal alternative might violate capacity constraints.

The contrast with fractional knapsack:

Interestingly, if we allow taking fractions of items, greedy by ratio DOES work! Why? Because we can always fill remaining capacity with a partial item—no capacity is wasted. The greedy choice never forecloses better options when fractions are allowed.

This illustrates the delicacy of the greedy choice property: a small change in problem constraints can enable or disable it.

The 0/1 Constraint Breaks Greedy

The inability to take partial items is what breaks greedy. With fractional knapsack, the greedy choice (best ratio) never leaves capacity unusable. With 0/1 knapsack, the greedy choice might consume capacity in a way that prevents better combinations.

Greedy as 'Collapsed DP': A Unifying View

There's an elegant way to understand the relationship between DP and greedy: greedy is DP with the search space collapsed.

In DP, we compute:

OPT(state) = min/max over choices { cost(choice) + OPT(next_state) }

We evaluate all choices to find the best. In greedy, we compute:

OPT(state) = cost(greedy_choice) + OPT(next_state_after_greedy_choice)

We evaluate one choice because the greedy choice property guarantees it's optimal.

Greedy exploits special structure:

When greedy choice property holds, the min/max over choices is always achieved by the greedy choice. So we skip the search—we know the answer without comparing.

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
// PROBLEM: Minimum coins to make amount
// 
// This problem has optimal substructure but SOMETIMES has greedy choice
// (depends on coin denominations).
 
// ═══════════════════════════════════════════════════════════
// DP SOLUTION (always works)
// ═══════════════════════════════════════════════════════════
function coinChangeDP(coins: number[], amount: number): number {
    const dp = new Array(amount + 1).fill(Infinity);
    dp[0] = 0;
    
    for (let a = 1; a <= amount; a++) {
        for (const coin of coins) {  // EXPLORE ALL CHOICES
            if (coin <= a && dp[a - coin] !== Infinity) {
                dp[a] = Math.min(dp[a], 1 + dp[a - coin]);
            }
        }
    }
    
    return dp[amount] === Infinity ? -1 : dp[amount];
}
 
// ═══════════════════════════════════════════════════════════
// GREEDY SOLUTION (only works for specific coin systems)
// ═══════════════════════════════════════════════════════════
function coinChangeGreedy(coins: number[], amount: number): number {
    // Sort descending to take largest coins first
    coins.sort((a, b) => b - a);
    
    let count = 0;
    let remaining = amount;
    
    for (const coin of coins) {
        // GREEDY CHOICE: Use as many of largest coin as possible
        const numCoins = Math.floor(remaining / coin);
        count += numCoins;
        remaining -= numCoins * coin;
    }
    
    return remaining === 0 ? count : -1;  // May fail!
}
 
// ═══════════════════════════════════════════════════════════
// WHEN DOES GREEDY WORK?
// ═══════════════════════════════════════════════════════════
// 
// Coins = [1, 5, 10, 25] (US coins): Greedy works ✓
//   Greedy for 41¢: 25 + 10 + 5 + 1 = 4 coins (optimal)
// 
// Coins = [1, 3, 4]: Greedy fails ✗
//   Greedy for 6: 4 + 1 + 1 = 3 coins
//   Optimal: 3 + 3 = 2 coins
// 
// The difference: US coins form a "canonical" system where
// greedy choice property holds. [1,3,4] does not.
 
// The structural insight:
// - DP explores all choices at each step
// - Greedy picks one choice per step
// - Greedy is correct when that one choice is always optimal
// - Greedy is "collapsed DP" — the search is trivially resolved

The collapse visualization:

DP Search Tree:         Greedy "Search" Tree:
      ┌── c1            
     ╱                          ┌── greedy choice ✓
S ──┼── c2                 S ──┤
     ╲                          └── (not explored)
      └── c3              
     (all explored,       (only greedy choice taken,
      best kept)           guaranteed optimal)

Greedy is DP where the search tree is collapsed to a single path—because we know that path leads to an optimum.

When to Seek Greedy

If you have a DP solution, ask: 'Is there always one clearly best choice at each step?' If yes, you might be able to prove greedy choice property and simplify to a greedy algorithm. The greedy algorithm will be faster (no need to explore all options) and simpler (no memoization table).

Choosing Between DP and Greedy: A Decision Framework

Given a new optimization problem, how do you decide whether to use DP or greedy? Here's a systematic framework:

Step 1: Verify optimal substructure

Both approaches need this. If optimal solutions contain optimal subsolutions, proceed. If not, neither DP nor greedy will work directly.

Step 2: Look for greedy choice property

Can you identify a locally optimal choice that's always safe? Can you prove (via exchange argument or stays-ahead argument) that this choice is part of some optimal solution?

Step 3: Try to find counterexamples

Before committing to greedy, actively seek examples where the greedy choice leads to suboptimal results. If you find one, greedy fails.

Step 4: Choose your approach

If greedy choice property holds: use greedy (simpler, faster)
If greedy choice property fails: use DP (guaranteed correct)

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
Start: Optimization Problem
          │
          ▼
┌─────────────────────────────┐
│ Does it have optimal        │
│ substructure?               │
└─────────────────────────────┘
          │
    ┌─────┴─────┐
    │           │
   Yes          No
    │           │
    ▼           ▼
Proceed    Neither DP nor Greedy
    │      works directly.
    │      Consider other approaches
    │      or reformulate.
    ▼
┌─────────────────────────────┐
│ Does greedy choice property │
│ hold?                       │
│                             │
│ (Can you prove local        │
│  best → globally safe?)     │
└─────────────────────────────┘
          │
    ┌─────┴─────┐
    │           │
   Yes          No / Unsure
    │           │
    ▼           ▼
┌──────────┐  ┌──────────────────────────────────┐
│  GREEDY  │  │ Use DYNAMIC PROGRAMMING          │
│          │  │                                  │
│ Fast     │  │ Slower (explores all choices)    │
│ Simple   │  │ but guaranteed correct           │
│ Often    │  │                                  │
│ O(n) or  │  │ Polynomial with memoization      │
│ O(n logn)│  └──────────────────────────────────┘
└──────────┘

Classic Problems: Greedy vs DP Classification
Problem	Optimal Substructure?	Greedy Choice Property?	Method
Activity Selection	✓ Yes	✓ Yes (earliest finish)	Greedy
Fractional Knapsack	✓ Yes	✓ Yes (best ratio)	Greedy
Huffman Coding	✓ Yes	✓ Yes (merge smallest)	Greedy
0/1 Knapsack	✓ Yes	✗ No (ratio fails)	DP
Longest Common Subsequence	✓ Yes	✗ No (no local indicator)	DP
Coin Change (general)	✓ Yes	✗ No (depends on coins)	DP
Minimum Spanning Tree	✓ Yes	✓ Yes (Kruskal/Prim)	Greedy
Shortest Path (Dijkstra)	✓ Yes	✓ Yes (nearest unvisited)	Greedy
Shortest Path (neg. edges)	✓ Yes	✗ No (local min unreliable)	DP (Bellman-Ford)
Matrix Chain Multiplication	✓ Yes	✗ No (no local indicator)	DP

When in Doubt, Use DP

If you're unsure whether greedy works, default to DP. DP is always correct (given optimal substructure). Greedy is a special-case optimization. It's better to have a slower correct solution than a fast wrong one.

Proving the Properties: Techniques for Verification

How do you rigorously verify whether a problem has these properties? Here are the standard proof techniques:

Proving Optimal Substructure:

Use the cut-and-paste argument (covered earlier). Assume you have an optimal solution. Identify a natural decomposition into subproblems. Assume (for contradiction) that a subsolution is not optimal for its subproblem. Show how to 'cut' that suboptimal piece and 'paste' in an optimal one, improving the overall solution. Conclude with contradiction.

Proving Greedy Choice Property:

Two main techniques:

Exchange Argument:
- Consider any optimal solution OPT that doesn't include the greedy choice.
- Show you can 'exchange' one of OPT's elements for the greedy choice.
- Prove the result is still optimal (not worse, possibly better).
- Conclude: greedy choice can always be part of an optimal solution.
Greedy Stays Ahead:
- Consider the greedy solution G and any optimal solution OPT.
- Prove by induction that after each step, G is 'at least as good' as OPT.
- Conclude: G ends up at least as good as OPT, so G is optimal.

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
Exchange Argument: Proving Greedy Choice Property
═══════════════════════════════════════════════════
 
Goal: Show greedy choice G is part of some optimal solution.
 
Structure:
1. Let OPT be an optimal solution.
 
2. Case 1: G ∈ OPT.
   Done! G is already in an optimal solution.
 
3. Case 2: G ∉ OPT.
   Let X be the element in OPT that we will exchange for G.
   (Choose X carefully — typically the "corresponding" element)
   
4. Define OPT' = (OPT - {X}) ∪ {G}
   (Remove X, add G)
   
5. Prove OPT' is valid:
   - Still feasible (satisfies constraints)
   - Value is ≥ OPT's value (so it's optimal too)
   
6. Conclude: OPT' is an optimal solution containing G.
   Therefore, greedy choice is safe. ∎
 
 
Example: Activity Selection
───────────────────────────
Greedy choice G = activity with earliest finish time.
 
If G ∉ OPT:
  Let A₁ = first activity in OPT.
  OPT' = (OPT - {A₁}) ∪ {G}
  
  Valid? 
    - G finishes earlier than A₁.
    - So G is compatible with all activities A₁ was compatible with.
    - OPT' has same number of activities as OPT.
    
  Conclusion: OPT' is optimal and contains G. ∎

Common Mistakes in Proofs

•Assuming what you want to prove: Don't assume the greedy solution is optimal; prove it.
•Forgetting feasibility: When exchanging elements, verify the new solution is still valid.
•Wrong decomposition: Optimal substructure depends on how you decompose. A bad decomposition might not have the property.
•One example isn't proof: Showing greedy works on one instance doesn't prove it works on all. You need a general argument.
•Missing counterexamples: Before attempting to prove greedy works, actively search for counterexamples.

Summary: The Greedy-DP Connection

We've explored the deep connection between optimal substructure in dynamic programming and greedy algorithms. This connection illuminates when each approach applies and how to choose between them.

Key Takeaways

•Both paradigms require optimal substructure: Without it, neither DP nor greedy can guarantee optimal solutions.
•Greedy requires an additional property: The greedy choice property—that a locally optimal choice is always part of some globally optimal solution.
•Greedy is 'collapsed DP': When greedy choice property holds, the DP search over all choices collapses to one obvious best choice.
•Same foundation, different power: Optimal substructure enables both, but they solve different problem classes.
•Prove before using greedy: Always verify greedy choice property via exchange argument or stays-ahead argument before trusting greedy.
•When in doubt, use DP: DP is always safe given optimal substructure. Greedy is an optimization for special cases.

What's next:

We've now seen what optimal substructure is, how to build with it, and how it connects to greedy algorithms. The final page of this module addresses a practical skill: how do you verify that a new problem has optimal substructure? We'll develop systematic techniques for this crucial analysis.

Page Complete

You now understand the fundamental relationship between DP and greedy through the lens of optimal substructure. This isn't just theory—it's the key to choosing the right algorithmic paradigm. When you recognize a problem has optimal substructure, ask: 'Does greedy choice work?' If yes, use greedy. If no, use DP. This decision framework will serve you throughout your algorithmic career.

3 / 4

Loading learning content...

Data Structures & AlgorithmsDynamic Programming

Optimal Substructure — The Foundation of Dynamic Programming

LevelIntermediate

Duration60 mins

TopicDynamic Programming

3 / 4

Connection to Greedy Optimal Substructure

Two Paradigms, One Property: The Optimal Substructure Connection

What You Will Master

Optimal Substructure: The Common Foundation

Let's establish clearly how both paradigms use optimal substructure.

In Dynamic Programming:

We decompose a problem into subproblems, solve each subproblem optimally, and combine the optimal subsolutions. The recurrence relation expresses this:

OPT(problem) = best_over_all_choices { cost(choice) + OPT(subproblem_after_choice) }

In Greedy Algorithms:

We also decompose into subproblems. But instead of exploring all choices, we immediately commit to the locally best choice:

OPT(problem) = greedy_choice + OPT(subproblem_after_greedy_choice)

Optimal Substructure Usage Comparison
Aspect	Dynamic Programming	Greedy Algorithm
Uses optimal substructure?	Yes (essential)	Yes (essential)
How subproblems are solved	All explored, best kept	Only one path explored
Choice exploration	Try all valid choices	Commit to best local choice
Guarantees optimality via	Exhaustive comparison	Greedy choice property + optimal substructure
Backtracking?	Implicit (via exploring all)	Never
Typical complexity	Polynomial (with memoization)	Often O(n log n) or O(n)

The Key Difference

The Greedy Choice Property: What Greedy Adds

Greedy algorithms work only when optimal substructure is paired with the greedy choice property:

A globally optimal solution can be obtained by making locally optimal (greedy) choices.

Formal statement:

Why this is powerful:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
WITHOUT Greedy Choice Property (need DP):
═══════════════════════════════════════
                    ┌─────── Choice A → leads to optimal path
State → explore → ├─────── Choice B → leads to suboptimal path  
                    └─────── Choice C → leads to optimal path
 
We don't know which choice leads to optimum without exploring all.
DP explores all, compares, picks best.
 
 
WITH Greedy Choice Property (can use Greedy):
═══════════════════════════════════════
                    ┌─────── Choice A (locally best) → guaranteed to be in SOME optimal
State → choose → ──┤
                    └─────── Other choices → might also be optimal, but A is sufficient
 
We KNOW the locally best choice is "safe" — no need to explore others.
Greedy commits to A immediately.
 
 
The Guarantee:
If "locally best" → "part of some optimal solution",
then we never need backtracking.
Make greedy choice → solve remaining subproblem optimally → done.

Requirements for Greedy to Work

•Optimal substructure: The problem breaks into subproblems, and optimal solutions contain optimal subsolutions.
•Greedy choice property: A locally optimal choice is always part of some globally optimal solution.
•No 'traps': Making the greedy choice never leads us to a state from which no optimal solution is reachable.

Optimal Substructure Alone Is Not Enough for Greedy

Case Study: Activity Selection (Greedy Works)

Let's examine a problem where greedy succeeds, and trace exactly how both optimal substructure and the greedy choice property enable it.

Problem: Activity Selection

Given n activities with start and finish times, select the maximum number of non-overlapping activities.

The greedy approach:

Sort activities by finish time
Always select the activity that finishes earliest (among compatible ones)
Repeat until no compatible activities remain

Why it works:

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
// Activity Selection: Greedy works because of BOTH properties
 
interface Activity {
    start: number;
    finish: number;
}
 
function maxActivities(activities: Activity[]): Activity[] {
    // Sort by finish time (enables greedy choice)
    activities.sort((a, b) => a.finish - b.finish);
    
    const selected: Activity[] = [];
    let lastFinish = -Infinity;
    
    for (const activity of activities) {
        if (activity.start >= lastFinish) {
            // GREEDY CHOICE: Select the next compatible activity
            // that finishes earliest
            selected.push(activity);
            lastFinish = activity.finish;
        }
    }
    
    return selected;
}
 
// ═══════════════════════════════════════════════════════════
// WHY GREEDY WORKS: PROOF SKETCH
// ═══════════════════════════════════════════════════════════
 
// PROPERTY 1: Greedy Choice Property
// 
// Claim: The activity that finishes first is part of SOME optimal solution.
// 
// Proof: Let A1 be the activity finishing first. Let OPT be any optimal solution.
// 
// Case 1: A1 ∈ OPT. Already part of optimum, done.
// 
// Case 2: A1 ∉ OPT. Let Aj be the first activity in OPT.
//   Since A1 finishes first overall, A1.finish ≤ Aj.finish.
//   So A1 is compatible with all activities that Aj is compatible with.
//   EXCHANGE: Replace Aj with A1 in OPT.
//   This is still valid (A1 ends earlier, so no new conflicts).
//   This is still optimal (same number of activities).
//   Now A1 is in an optimal solution. ∎
 
// PROPERTY 2: Optimal Substructure
// 
// After selecting the earliest-finishing activity A1:
// Remaining problem: select max activities from those starting after A1.finish.
// 
// Claim: Optimal solution = {A1} ∪ OPT(remaining activities).
// 
// Proof: If OPT(remaining) weren't optimal for the remaining activities,
// we could improve it, improving the overall count.
// This contradicts that we have an optimal overall solution.
// So OPT(remaining) MUST be optimal. ∎
 
// Together: Greedy choice is safe + remaining is solved optimally = optimal!

The interplay of both properties:

Greedy choice property tells us: selecting the earliest-finishing activity is safe—it's part of some optimal solution.
Optimal substructure tells us: once we've made that choice, the remaining problem is a smaller instance of the same problem, and we should solve it optimally.
Greedy recursion: We apply the greedy choice repeatedly, each time reducing to a smaller subproblem, confident that local + optimal-remaining = global optimal.

Case Study: 0/1 Knapsack (Greedy Fails, DP Works)

Now let's examine a problem where greedy fails despite optimal substructure being present.

Problem: 0/1 Knapsack

Does it have optimal substructure? Yes!

Why doesn't greedy work?

The natural greedy strategies fail:

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
69
70
// 0/1 Knapsack: Optimal substructure ✓, Greedy choice property ✗
 
// GREEDY ATTEMPT 1: Take highest value items first
// 
// Counterexample:
// Capacity = 10
// Items: A(weight=6, value=30), B(weight=5, value=25), C(weight=5, value=24)
// 
// Greedy by value: Take A (value 30, weight 6). Remaining capacity: 4.
// No other item fits. Total: 30.
// 
// Optimal: Take B + C (value 25+24=49, weight 10). Total: 49.
// 
// Greedy by value is WRONG. ✗
 
// GREEDY ATTEMPT 2: Take by value-to-weight ratio
// 
// Counterexample:
// Capacity = 10
// Items: A(w=1, v=6, ratio=6), B(w=10, v=50, ratio=5)
// 
// Greedy by ratio: Take A (ratio 6). Remaining capacity: 9.
// B doesn't fit. Total: 6.
// 
// Optimal: Take B alone. Total: 50.
// 
// Greedy by ratio is WRONG. ✗
 
// GREEDY ATTEMPT 3: Take smallest weight items first
//
// Counterexample:
// Capacity = 10
// Items: A(w=1, v=1), B(w=9, v=100)
//
// Greedy by weight: Take A. Remaining capacity: 9.
// Take B. Total: 101. (Happens to work here, but...)
//
// Different example:
// Items: A(w=1, v=1), B(w=1, v=1), C(w=1, v=1), ..., ten items of (w=1, v=1)
// Plus: D(w=10, v=50)
//
// Greedy by weight: Take all small items. Total: 10.
// Optimal: Take D. Total: 50.
//
// Greedy by weight is WRONG. ✗
 
// CONCLUSION:
// No greedy strategy works for 0/1 knapsack.
// We MUST use DP to find the optimal solution.
 
function knapsackDP(weights: number[], values: number[], capacity: number): number {
    const n = weights.length;
    const dp = Array.from({length: n + 1}, () => Array(capacity + 1).fill(0));
    
    for (let i = 1; i <= n; i++) {
        for (let w = 0; w <= capacity; w++) {
            // Optimal substructure is used here:
            // We trust dp[i-1][...] to be optimal for those subproblems
            dp[i][w] = dp[i - 1][w];  // Exclude item i
            if (weights[i - 1] <= w) {
                dp[i][w] = Math.max(
                    dp[i][w], 
                    values[i - 1] + dp[i - 1][w - weights[i - 1]]  // Include item i
                );
            }
        }
    }
    
    return dp[n][capacity];
}

Why greedy choice property fails:

The core issue is that the locally best choice isn't always globally safe. Consider items sorted by value-to-weight ratio:

The item with best ratio might use capacity needed for a combination of items that together provide more value.
Making the greedy choice can foreclose better options.
There's no exchange argument that works: swapping a greedy item for the optimal alternative might violate capacity constraints.

The contrast with fractional knapsack:

This illustrates the delicacy of the greedy choice property: a small change in problem constraints can enable or disable it.

The 0/1 Constraint Breaks Greedy

Greedy as 'Collapsed DP': A Unifying View

There's an elegant way to understand the relationship between DP and greedy: greedy is DP with the search space collapsed.

In DP, we compute:

OPT(state) = min/max over choices { cost(choice) + OPT(next_state) }

We evaluate all choices to find the best. In greedy, we compute:

OPT(state) = cost(greedy_choice) + OPT(next_state_after_greedy_choice)

We evaluate one choice because the greedy choice property guarantees it's optimal.

Greedy exploits special structure:

When greedy choice property holds, the min/max over choices is always achieved by the greedy choice. So we skip the search—we know the answer without comparing.

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
// PROBLEM: Minimum coins to make amount
// 
// This problem has optimal substructure but SOMETIMES has greedy choice
// (depends on coin denominations).
 
// ═══════════════════════════════════════════════════════════
// DP SOLUTION (always works)
// ═══════════════════════════════════════════════════════════
function coinChangeDP(coins: number[], amount: number): number {
    const dp = new Array(amount + 1).fill(Infinity);
    dp[0] = 0;
    
    for (let a = 1; a <= amount; a++) {
        for (const coin of coins) {  // EXPLORE ALL CHOICES
            if (coin <= a && dp[a - coin] !== Infinity) {
                dp[a] = Math.min(dp[a], 1 + dp[a - coin]);
            }
        }
    }
    
    return dp[amount] === Infinity ? -1 : dp[amount];
}
 
// ═══════════════════════════════════════════════════════════
// GREEDY SOLUTION (only works for specific coin systems)
// ═══════════════════════════════════════════════════════════
function coinChangeGreedy(coins: number[], amount: number): number {
    // Sort descending to take largest coins first
    coins.sort((a, b) => b - a);
    
    let count = 0;
    let remaining = amount;
    
    for (const coin of coins) {
        // GREEDY CHOICE: Use as many of largest coin as possible
        const numCoins = Math.floor(remaining / coin);
        count += numCoins;
        remaining -= numCoins * coin;
    }
    
    return remaining === 0 ? count : -1;  // May fail!
}
 
// ═══════════════════════════════════════════════════════════
// WHEN DOES GREEDY WORK?
// ═══════════════════════════════════════════════════════════
// 
// Coins = [1, 5, 10, 25] (US coins): Greedy works ✓
//   Greedy for 41¢: 25 + 10 + 5 + 1 = 4 coins (optimal)
// 
// Coins = [1, 3, 4]: Greedy fails ✗
//   Greedy for 6: 4 + 1 + 1 = 3 coins
//   Optimal: 3 + 3 = 2 coins
// 
// The difference: US coins form a "canonical" system where
// greedy choice property holds. [1,3,4] does not.
 
// The structural insight:
// - DP explores all choices at each step
// - Greedy picks one choice per step
// - Greedy is correct when that one choice is always optimal
// - Greedy is "collapsed DP" — the search is trivially resolved

The collapse visualization:

DP Search Tree:         Greedy "Search" Tree:
      ┌── c1            
     ╱                          ┌── greedy choice ✓
S ──┼── c2                 S ──┤
     ╲                          └── (not explored)
      └── c3              
     (all explored,       (only greedy choice taken,
      best kept)           guaranteed optimal)

Greedy is DP where the search tree is collapsed to a single path—because we know that path leads to an optimum.

When to Seek Greedy

Choosing Between DP and Greedy: A Decision Framework

Given a new optimization problem, how do you decide whether to use DP or greedy? Here's a systematic framework:

Step 1: Verify optimal substructure

Both approaches need this. If optimal solutions contain optimal subsolutions, proceed. If not, neither DP nor greedy will work directly.

Step 2: Look for greedy choice property

Can you identify a locally optimal choice that's always safe? Can you prove (via exchange argument or stays-ahead argument) that this choice is part of some optimal solution?

Step 3: Try to find counterexamples

Before committing to greedy, actively seek examples where the greedy choice leads to suboptimal results. If you find one, greedy fails.

Step 4: Choose your approach

If greedy choice property holds: use greedy (simpler, faster)
If greedy choice property fails: use DP (guaranteed correct)

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
Start: Optimization Problem
          │
          ▼
┌─────────────────────────────┐
│ Does it have optimal        │
│ substructure?               │
└─────────────────────────────┘
          │
    ┌─────┴─────┐
    │           │
   Yes          No
    │           │
    ▼           ▼
Proceed    Neither DP nor Greedy
    │      works directly.
    │      Consider other approaches
    │      or reformulate.
    ▼
┌─────────────────────────────┐
│ Does greedy choice property │
│ hold?                       │
│                             │
│ (Can you prove local        │
│  best → globally safe?)     │
└─────────────────────────────┘
          │
    ┌─────┴─────┐
    │           │
   Yes          No / Unsure
    │           │
    ▼           ▼
┌──────────┐  ┌──────────────────────────────────┐
│  GREEDY  │  │ Use DYNAMIC PROGRAMMING          │
│          │  │                                  │
│ Fast     │  │ Slower (explores all choices)    │
│ Simple   │  │ but guaranteed correct           │
│ Often    │  │                                  │
│ O(n) or  │  │ Polynomial with memoization      │
│ O(n logn)│  └──────────────────────────────────┘
└──────────┘

Classic Problems: Greedy vs DP Classification
Problem	Optimal Substructure?	Greedy Choice Property?	Method
Activity Selection	✓ Yes	✓ Yes (earliest finish)	Greedy
Fractional Knapsack	✓ Yes	✓ Yes (best ratio)	Greedy
Huffman Coding	✓ Yes	✓ Yes (merge smallest)	Greedy
0/1 Knapsack	✓ Yes	✗ No (ratio fails)	DP
Longest Common Subsequence	✓ Yes	✗ No (no local indicator)	DP
Coin Change (general)	✓ Yes	✗ No (depends on coins)	DP
Minimum Spanning Tree	✓ Yes	✓ Yes (Kruskal/Prim)	Greedy
Shortest Path (Dijkstra)	✓ Yes	✓ Yes (nearest unvisited)	Greedy
Shortest Path (neg. edges)	✓ Yes	✗ No (local min unreliable)	DP (Bellman-Ford)
Matrix Chain Multiplication	✓ Yes	✗ No (no local indicator)	DP

When in Doubt, Use DP

Proving the Properties: Techniques for Verification

How do you rigorously verify whether a problem has these properties? Here are the standard proof techniques:

Proving Optimal Substructure:

Proving Greedy Choice Property:

Two main techniques:

Exchange Argument:
- Consider any optimal solution OPT that doesn't include the greedy choice.
- Show you can 'exchange' one of OPT's elements for the greedy choice.
- Prove the result is still optimal (not worse, possibly better).
- Conclude: greedy choice can always be part of an optimal solution.
Greedy Stays Ahead:
- Consider the greedy solution G and any optimal solution OPT.
- Prove by induction that after each step, G is 'at least as good' as OPT.
- Conclude: G ends up at least as good as OPT, so G is optimal.

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
Exchange Argument: Proving Greedy Choice Property
═══════════════════════════════════════════════════
 
Goal: Show greedy choice G is part of some optimal solution.
 
Structure:
1. Let OPT be an optimal solution.
 
2. Case 1: G ∈ OPT.
   Done! G is already in an optimal solution.
 
3. Case 2: G ∉ OPT.
   Let X be the element in OPT that we will exchange for G.
   (Choose X carefully — typically the "corresponding" element)
   
4. Define OPT' = (OPT - {X}) ∪ {G}
   (Remove X, add G)
   
5. Prove OPT' is valid:
   - Still feasible (satisfies constraints)
   - Value is ≥ OPT's value (so it's optimal too)
   
6. Conclude: OPT' is an optimal solution containing G.
   Therefore, greedy choice is safe. ∎
 
 
Example: Activity Selection
───────────────────────────
Greedy choice G = activity with earliest finish time.
 
If G ∉ OPT:
  Let A₁ = first activity in OPT.
  OPT' = (OPT - {A₁}) ∪ {G}
  
  Valid? 
    - G finishes earlier than A₁.
    - So G is compatible with all activities A₁ was compatible with.
    - OPT' has same number of activities as OPT.
    
  Conclusion: OPT' is optimal and contains G. ∎

Common Mistakes in Proofs

•Assuming what you want to prove: Don't assume the greedy solution is optimal; prove it.
•Forgetting feasibility: When exchanging elements, verify the new solution is still valid.
•Wrong decomposition: Optimal substructure depends on how you decompose. A bad decomposition might not have the property.
•One example isn't proof: Showing greedy works on one instance doesn't prove it works on all. You need a general argument.
•Missing counterexamples: Before attempting to prove greedy works, actively search for counterexamples.

Summary: The Greedy-DP Connection

We've explored the deep connection between optimal substructure in dynamic programming and greedy algorithms. This connection illuminates when each approach applies and how to choose between them.

Key Takeaways

•Both paradigms require optimal substructure: Without it, neither DP nor greedy can guarantee optimal solutions.
•Greedy requires an additional property: The greedy choice property—that a locally optimal choice is always part of some globally optimal solution.
•Greedy is 'collapsed DP': When greedy choice property holds, the DP search over all choices collapses to one obvious best choice.
•Same foundation, different power: Optimal substructure enables both, but they solve different problem classes.
•Prove before using greedy: Always verify greedy choice property via exchange argument or stays-ahead argument before trusting greedy.
•When in doubt, use DP: DP is always safe given optimal substructure. Greedy is an optimization for special cases.

What's next:

Page Complete

3 / 4