How Does Greedy Choice Relate to Optimal Substructure?
Learn why optimal substructure alone does not justify greedy algorithms, and when DP is required instead, with proof techniques.
Expected Interview Answer
A greedy algorithm only produces a globally optimal solution when a problem has both the greedy-choice property — a locally optimal choice at each step leads toward a globally optimal solution — and optimal substructure, meaning an optimal solution to the whole problem contains optimal solutions to its subproblems, which is why the same optimal-substructure requirement also underlies dynamic programming.
Optimal substructure alone is not enough to justify greedy: DP problems like 0/1 knapsack and longest common subsequence have optimal substructure but lack the greedy-choice property, since the best local decision can foreclose a better global solution, so they need to explore multiple subproblem combinations via memoization or tabulation. Greedy works only when you can prove that some locally optimal first choice is always part of at least one globally optimal solution, letting you commit to it without backtracking and reduce the problem to one smaller subproblem instead of many. Activity selection, Huffman coding, and Dijkstra’s algorithm (with non-negative weights) are classic examples where an exchange argument or matroid structure proves the greedy-choice property holds. When a problem has optimal substructure but greedy fails an exchange-argument proof, dynamic programming is the correct tool, because it safely considers all relevant subproblem choices instead of committing early.
- Explains exactly when greedy algorithms are provably correct
- Clarifies why some optimal-substructure problems still need DP
- Gives a proof technique (exchange argument) for validating greedy
- Prevents applying greedy to problems where it silently gives wrong answers
AI Mentor Explanation
Optimal substructure is like knowing that a team’s best possible innings score is built from the best possible score achievable from each remaining over onward — the whole optimal innings is made of optimal sub-innings. But the greedy-choice property is a stronger claim: that always playing the single highest-expected-run shot available right now is guaranteed to be part of that optimal innings. Sometimes that is true, like always taking a free run when offered with no risk. But sometimes swinging for a boundary now costs a wicket that ruins the rest of the innings, meaning the locally best shot is not part of the globally best innings, which is exactly why some batting strategies need full look-ahead planning (dynamic programming) instead of shot-by-shot greedy choices.
Step-by-Step Explanation
Step 1
Confirm optimal substructure
Check that an optimal solution to the whole problem is built from optimal solutions to its subproblems.
Step 2
Test the greedy-choice property
Ask whether a locally optimal first choice is guaranteed to be part of some globally optimal solution.
Step 3
Prove it with an exchange argument
Show that any optimal solution can be transformed to include the greedy choice without reducing its value.
Step 4
Fall back to DP if greedy fails
If no such proof holds, use memoization or tabulation to safely explore multiple subproblem combinations instead of committing early.
What Interviewer Expects
- Distinguish optimal substructure (shared by both greedy and DP) from the greedy-choice property (greedy-only)
- Give at least one example where optimal substructure holds but greedy fails (e.g. 0/1 knapsack)
- Give at least one example where greedy works and explain why (e.g. activity selection, Huffman coding)
- Mention the exchange argument as the standard proof technique for greedy correctness
Common Mistakes
- Assuming any problem with optimal substructure can be solved greedily
- Confusing greedy correctness with greedy being “simpler” or “faster” — correctness must be proven, not assumed
- Failing to give a concrete counterexample where greedy fails despite optimal substructure
- Not mentioning that DP explores multiple subproblem choices while greedy commits to one
Best Answer (HR Friendly)
“Optimal substructure means a big problem’s best solution is made up of the best solutions to its smaller pieces — both greedy algorithms and dynamic programming rely on that. But greedy only works when you can also prove that the single best choice right now is always part of the best overall answer. When that extra guarantee does not hold, like in the 0/1 knapsack problem, you need dynamic programming instead, because it safely considers multiple possibilities rather than committing early to one choice.”
Code Example
# Activity selection: optimal substructure + greedy-choice property both hold
def activity_selection(activities):
# activities: list of (start, finish), sorted by finish time
activities = sorted(activities, key=lambda a: a[1])
selected = [activities[0]]
last_finish = activities[0][1]
for start, finish in activities[1:]:
if start >= last_finish:
selected.append((start, finish))
last_finish = finish
return selected
# 0/1 knapsack: optimal substructure holds, but greedy-choice property FAILS
# so we must explore both include/exclude choices via DP
def knapsack_01(weights, values, capacity):
n = len(weights)
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for cap in range(capacity + 1):
dp[i][cap] = dp[i - 1][cap]
if weights[i - 1] <= cap:
dp[i][cap] = max(
dp[i][cap],
dp[i - 1][cap - weights[i - 1]] + values[i - 1],
)
return dp[n][capacity]Follow-up Questions
- Can you prove the greedy-choice property for activity selection using an exchange argument?
- Why does greedy-by-ratio fail for 0/1 knapsack but succeed for fractional knapsack?
- How does matroid theory formalize when greedy algorithms are guaranteed correct?
- Give an example of a problem with neither optimal substructure nor the greedy-choice property.
MCQ Practice
1. What does “optimal substructure” mean?
Optimal substructure means the global optimum is composed of optimal solutions to smaller subproblems — a property shared by greedy and DP problems alike.
2. Which statement correctly distinguishes greedy algorithms from dynamic programming?
Greedy is correct only when the extra greedy-choice property holds; DP works with just optimal substructure by exploring subproblem combinations.
3. Which is a standard technique for proving the greedy-choice property holds for a problem?
An exchange argument shows any optimal solution can be transformed to include the greedy choice without losing optimality.
Flash Cards
What is optimal substructure? — An optimal solution to a problem is composed of optimal solutions to its subproblems.
What extra property must hold for greedy to be correct, beyond optimal substructure? — The greedy-choice property: a locally optimal choice is guaranteed to be part of some globally optimal solution.
Name a problem with optimal substructure where greedy fails. — 0/1 knapsack — it requires dynamic programming instead.
What proof technique validates the greedy-choice property? — An exchange argument, showing any optimal solution can be adjusted to include the greedy choice at no cost.