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

Concept:
• Both Greedy algorithms and Dynamic Programming (DP) are strategies used for solving optimization problems.
• They share certain theoretical requirements but differ in how they build solutions.

Step 1: Identify shared requirements
An optimization problem must exhibit Optimal Substructure to be solved by either method. This means an optimal solution to the problem contains within it optimal solutions to its subproblems.
Therefore, Statement (A) is correct and Statement (C) is false.

Step 2: Identify differences

• Overlapping Subproblems: This is a requirement for DP to be efficient (so results can be memoized). Greedy does not require this; it makes a local choice and never re-visits subproblems. Thus, (B) is false.
• Greedy Choice Property: Greedy works only if a local optimal choice leads to a global optimal. Many problems (like 0/1 knapsack) do not satisfy this, so Greedy does NOT always give an optimal solution. Thus, (D) is false.