Answer the following: (i) Compare dynamic programming and greedy algorithms in terms of their problem-solving approaches, solution spaces, and efficie

Question

Answer the following:
(i) Compare dynamic programming and greedy algorithms in terms of their problem-solving approaches, solution spaces, and efficiency.
(ii) Discuss scenarios where dynamic programming is necessary because greedy strategies fail. Use suitable problem examples to support your explanation.
(iii) Explain how overlapping subproblems and optimal substructure are utilized in dynamic programming.

Accepted Answer

## Dynamic Programming vs Greedy Algorithms

| Aspect | Greedy | Dynamic Programming (DP) |
|---|---|---|
| **Principle** | Make locally optimal choice at each step, never reconsider. | Break into overlapping subproblems, solve each once, combine via recurrence with optimal substructure. |
| **Subproblems** | One path, no overlapping storage. | Many overlapping, stored in table (memoization/tabulation). |
| **Optimality** | Works only if problem has *greedy-choice property* + optimal substructure (e.g., MST, Fractional Knapsack, Huffman). Fails otherwise (0/1 Knapsack). | Works if *optimal substructure* + *overlapping subproblems*; yields global optimum (e.g., 0/1 Knapsack, LCS, Matrix Chain). |
| **Approach** | Top-down, irrevocable decisions. | Bottom-up or top-down memoized, exhaustive over subproblem space. |
| **Complexity** | Usually faster: $O(n\log n)$ or $O(n)$. | Usually higher: $O(n^2)$, $O(nW)$ etc due to table. |
| **Example Success** | Prim's $O(E\log V)$, Dijkstra (non-negative), Fractional Knapsack $O(n\log n)$. | 0/1 Knapsack $O(nW)$, Matrix Chain $O(n^3)$, LCS $O(mn)$, Floyd $O(V^3)$. |
| **Example Failure** | 0/1 Knapsack: greedy by ratio fails (e.g., capacity 50, items (60,10),(100,20),(120,30) → greedy picks 60+100 vs optimal 100+120). | Greedy would be overkill where greedy suffices (Huffman both greedily optimal, DP not needed). |

### How to Choose
- Try greedy: prove greedy-choice + optimal substructure → simplest.
- If greedy fails (need to consider all combinations), use DP.

### Code Contrast: 0/1 Knapsack
- Greedy (ratio): sort by $p_i/w_i$ and take until full — **not optimal** for 0/1.
- DP: `dp[i][w]=max(dp[i-1][w], dp[i-1][w-w_i]+p_i)` → optimal.

Aspect	Greedy	Dynamic Programming (DP)
Principle	Make locally optimal choice at each step, never reconsider.	Break into overlapping subproblems, solve each once, combine via recurrence with optimal substructure.
Subproblems	One path, no overlapping storage.	Many overlapping, stored in table (memoization/tabulation).
Optimality	Works only if problem has greedy-choice property + optimal substructure (e.g., MST, Fractional Knapsack, Huffman). Fails otherwise (0/1 Knapsack).	Works if optimal substructure + overlapping subproblems; yields global optimum (e.g., 0/1 Knapsack, LCS, Matrix Chain).
Approach	Top-down, irrevocable decisions.	Bottom-up or top-down memoized, exhaustive over subproblem space.
Complexity	Usually faster: $O(n\log n)$ or $O(n)$ .	Usually higher: $O(n^2)$ , $O(nW)$ etc due to table.
Example Success	Prim's $O(E\log V)$ , Dijkstra (non-negative), Fractional Knapsack $O(n\log n)$ .	0/1 Knapsack $O(nW)$ , Matrix Chain $O(n^3)$ , LCS $O(mn)$ , Floyd $O(V^3)$ .
Example Failure	0/1 Knapsack: greedy by ratio fails (e.g., capacity 50, items (60,10),(100,20),(120,30) → greedy picks 60+100 vs optimal 100+120).	Greedy would be overkill where greedy suffices (Huffman both greedily optimal, DP not needed).

Dynamic Programming vs Greedy Algorithms

How to Choose

Code Contrast: 0/1 Knapsack

Similar questions

Pocketly on Android