Dynamic Programming and Greedy Algorithms: Comparative Analysis, Failure Cases, and Core DP Properties

Dynamic programming and greedy algorithms are two major paradigms for solving optimization problems and related decision tasks. Although both often rely on optimal substructure, they differ fundamentally in how they explore the solution space, justify correctness, and trade time for memory.

A greedy algorithm commits early: at each step, it selects the locally best-looking option and never revisits that decision. This works only when the problem has the greedy-choice property in addition to optimal substructure. Dynamic programming, by contrast, systematically evaluates subproblems, stores their results, and combines them to guarantee a global optimum when the problem has optimal substructure and overlapping subproblems.

In practice, greedy methods are usually simpler and more memory-efficient, while dynamic programming is more general and more reliable for problems where local choices can block the global optimum.

The comparison can be summarized as follows:

A useful conceptual distinction is that greedy algorithms try to avoid exploring combinations, whereas dynamic programming succeeds by representing them compactly through states and recurrence relations.

Introduction to Algorithms, Chapter 17: Greedy Algorithms - Explains greedy-choice property, optimal substructure, and contrasts greedy with dynamic programming. Greedy Algorithms General Structure - GeeksforGeeks - Summarizes when greedy and DP apply and highlights required structural properties. Greedy Algorithms lecture notes - Notes that DP tabulates overlapping subproblems and often reduces exponential recursion to polynomial time. Analysis of Algorithms: Lecture 11 - Describes optimal substructure, overlapping subproblems, and the standard DP design steps.

(i) Comparing Dynamic Programming and Greedy Algorithms

From a problem-solving perspective, greedy algorithms operate by making an irrevocable local decision that appears best at the current moment. Their correctness depends on proving that this local decision is always compatible with some global optimum. Dynamic programming does not assume that the first attractive-looking choice is safe. Instead, it models the problem as a collection of states, computes the best value for each state, and derives the final answer from those stored values.

This difference leads to a major contrast in solution space handling. Greedy methods effectively follow a single promising path through the solution space. Dynamic programming represents a much broader set of possibilities, but compresses them by observing that many distinct partial solutions reduce to the same state. Thus, DP is not brute force: it avoids enumerating all complete solutions by merging equivalent subproblems.

Efficiency also differs in an important way. If a valid greedy strategy exists, it is often asymptotically better. Many classical greedy algorithms run in $O(n \log n)$ due to sorting or priority queues, with relatively low memory overhead. Dynamic programming commonly uses $O(n^2)$, $O(nW)$, or similar table-filling costs depending on the state definition, and may also require substantial storage. However, compared with naive recursion, DP can transform exponential computation into polynomial time by solving each recurring subproblem once.

A concise theoretical view is:

$$\text{Greedy: } \text{commit locally} \Rightarrow \text{hope local optimum implies global optimum}$$ $$\text{DP: } \text{solve all relevant states once} \Rightarrow \text{combine them into a global optimum}$$

This is why the set of problems solvable greedily is generally a subset of those solvable by dynamic programming.

(ii) When Dynamic Programming Is Necessary Because Greedy Fails

Dynamic programming becomes necessary when a locally optimal decision can prevent the globally optimal solution. This usually happens when decisions interact across stages, so the best immediate choice is not part of the best overall combination.

Example 1: Coin Change with Non-Canonical Denominations

Consider coin denominations $\{1, 3, 4\}$ and a target value of $6$. A greedy strategy that repeatedly takes the largest possible coin chooses:

$$4 + 1 + 1$$

This uses $3$ coins. But the optimal solution is:

$$3 + 3$$

which uses only $2$ coins. The failure occurs because choosing $4$ first appears locally attractive, yet it leaves a remainder that is expensive to finish. Dynamic programming succeeds by evaluating all relevant smaller amounts and storing the minimum coins needed for each amount.

A standard DP recurrence for minimum coin count is:

$$dp[x] = 1 + \min_{c \in C,\; c \le x} dp[x-c]$$

with base case $dp[0]=0$.

Example 2: $0/1$ Knapsack

In the 0/1 knapsack problem, each item is either taken or not taken. A greedy rule such as choosing the highest value-to-weight ratio works for fractional knapsack, but it does not always work for $0/1$ knapsack.

A classic counterexample uses capacity $50$ and items:

A greedy ratio-based choice picks Items $1$ and $2$ for total value $160$, leaving no room for Item $3$. But the optimal solution is Items $2$ and $3$, with total weight $50$ and total value $220$. Here, local ranking does not capture the combinational structure of the problem.

Dynamic programming handles this by comparing both possibilities for each item: include it or exclude it. The recurrence is:

$$dp[i][w] = \max\big(dp[i-1][w],\; v_i + dp[i-1][w-w_i]\big)$$

when $w_i \le w$.

Why Greedy Fails in These Cases

Greedy fails when:

• future consequences of a local choice matter strongly,
• combinations dominate isolated decisions,
• the problem lacks the greedy-choice property,
• partial choices cannot be judged correctly without considering remaining capacity, remainder, or later options.2

By contrast, dynamic programming is designed for precisely these situations because it preserves multiple subproblem outcomes until enough information exists to decide which one is globally best.

Footnotes

1. Mastering Greedy Algorithms: Key Examples, Interview Tips, and When They Work - Gives a clear counterexample where greedy coin change fails for denominations $\\{1,3,4\\}$ and amount $6$. ↩ ↩² ↩³

2. Greedy Algorithms: Concept, Examples, and Applications - Shows why greedy succeeds for fractional knapsack but can fail for $0/1$ knapsack with a standard counterexample. ↩ ↩² ↩³ ↩⁴

(iii) How Overlapping Subproblems and Optimal Substructure Are Used in Dynamic Programming

Dynamic programming relies on two foundational properties.

1. Optimal Substructure

A problem has optimal substructure when an optimal solution to the whole problem can be assembled from optimal solutions to its subproblems. This gives the logical basis for writing a recurrence. For example, in shortest-path formulations, if a shortest path from $u$ to $v$ passes through $k$, then the path segment from $u$ to $k$ must itself be shortest; otherwise the total path could be improved, contradicting optimality.2

In DP design, optimal substructure is used to define a recurrence relation. The recurrence expresses the value of a state in terms of smaller states. Once this relation is valid, the problem can be solved by building upward from base cases.

2. Overlapping Subproblems

A problem has overlapping subproblems when the same smaller states reappear many times in the recursive decomposition. Without overlap, plain divide-and-conquer may be sufficient; with overlap, naive recursion wastes time recomputing the same values repeatedly.

The Fibonacci recurrence is the standard illustration:

$$F(n) = F(n-1) + F(n-2)$$

A naive recursive algorithm recomputes values such as $F(n-2)$, $F(n-3)$, and so on many times. Dynamic programming stores each computed value once, either through memoization or tabulation, reducing redundant work dramatically.

How the Two Properties Work Together

Optimal substructure tells us that solving subproblems is sufficient for solving the larger problem. Overlapping subproblems tell us that storing those subproblem solutions is worthwhile computationally.

A general dynamic programming workflow is:

1. Define the state.
2. Prove optimal substructure.
3. Write the recurrence.
4. Identify base cases.
5. Compute each state once using memoization or tabulation.
6. Reconstruct the final solution if needed.

This can be formalized as:

$$\text{Answer} = \operatorname{opt}(S)$$

where $S$ is the original state and

$$\operatorname{opt}(S) = \best_{a \in A(S)} \big(\text{immediate contribution of } a + \operatorname{opt}(\text{next state after } a)\big)$$

The exact operator may be $\min$ or $\max$, depending on the objective.

Footnotes

1. Optimal Substructure Property in Dynamic Programming - GeeksforGeeks - Explains optimal substructure with shortest-path style examples and contrasts it with cases lacking the property. ↩ ↩²

2. Dynamic Programming I (CMU lecture notes) - Discusses how optimal substructure supports DP recurrences and illustrates shortest-path reasoning. ↩ ↩²

Synthesis

The relationship between these paradigms can now be stated precisely. Greedy algorithms are attractive because they are fast, direct, and often elegant, but they only work when a problem admits a provably safe local-choice rule. Dynamic programming is more systematic: it explores the decision structure through states, exploits overlapping subproblems to avoid recomputation, and uses optimal substructure to assemble a globally optimal solution.

Thus:

• For part (i), greedy and dynamic programming differ in decision philosophy, exploration of the solution space, and resource usage.
• For part (ii), dynamic programming is necessary in problems like non-canonical coin change and $0/1$ knapsack because local choices can be globally misleading.2
• For part (iii), optimal substructure justifies the recurrence, while overlapping subproblems justifies caching or tabulation.

A compact rule of thumb is:

$$\text{Use greedy if you can prove local choices are globally safe;}$$ $$\text{use DP if you must compare many dependent partial solutions efficiently.}$$

Footnotes

1. Mastering Greedy Algorithms: Key Examples, Interview Tips, and When They Work - Gives a clear counterexample where greedy coin change fails for denominations $\\{1,3,4\\}$ and amount $6$. ↩

2. Greedy Algorithms: Concept, Examples, and Applications - Shows why greedy succeeds for fractional knapsack but can fail for $0/1$ knapsack with a standard counterexample. ↩

3. Dynamic Programming I (CMU lecture notes) - Discusses how optimal substructure supports DP recurrences and illustrates shortest-path reasoning. ↩