Question

Which of the following statement is true ?

• A. Greedy and dynamic programming both require optimal sub structure
• B. Greedy requires overlapping sub problems
• C. Dynamic programming does not require optimal sub structure
• D. Greedy always gives optimal solution

Hint:

Optimal Substructure is the "parent" requirement for both. Overlapping Subproblems is the specific "child" requirement that distinguishes DP from simple recursion or greedy.

Answer 1

The Correct Option is A

Greedy algorithms and Dynamic Programming (DP) are two major algorithmic paradigms used for optimization problems. 1. Optimal Substructure: Both Greedy and Dynamic Programming require the problem to have optimal substructure. This means that an optimal solution to the overall problem contains within it optimal solutions to its subproblems. 2. Distinguishing Characteristics:
• Overlapping Subproblems: This is a requirement for Dynamic Programming, not Greedy. DP solves subproblems and stores results (memoization) to avoid re-computation.
• Greedy Choice Property: Greedy algorithms make a locally optimal choice at each step with the hope that it leads to a globally optimal solution. 3. Why other options are false:
• Option (2): Greedy does not require overlapping subproblems; it moves forward without looking back at previous states.
• Option (3): DP absolutely requires optimal substructure to function.
• Option (4): Greedy does not always yield an optimal solution (e.g., 0/1 Knapsack, Coin Change with arbitrary denominations).