Consider the following steps: š¯‘†1: Characterize the structure of an optimalā€¦
2019
Consider the following steps:
š¯‘†1: Characterize the structure of an optimal solution
š¯‘†2: Compute the value of an optimal solution in bottom-up fashion
Which of the following step(s) is/are common to both dynamic programming and greedy algorithms?
- A.
OnlyĀ š¯‘†1
- B.
OnlyĀ š¯‘†2
- C.
BothĀ š¯‘†1Ā andĀ š¯‘†2
- D.
NeitherĀ š¯‘†1Ā norĀ š¯‘†2
Attempted by 365 students.
Show answer & explanation
Correct answer: A
Answer: The step that is common to both approaches is to characterize the structure of an optimal solution (the optimal substructure property).
Why this is common: Both dynamic programming and greedy algorithms depend on the optimal substructure property ā€” an optimal solution can be built from optimal solutions to subproblems or from optimal local choices.
Why the bottom-up computation is not common: Computing the value of an optimal solution in bottom-up fashion is a hallmark of dynamic programming (or its top-down memoized variant). Greedy algorithms typically do not compute all subproblem values bottom-up; they make a sequence of locally optimal choices based on the greedy-choice property.
Concrete example: For coin change, dynamic programming finds the minimum coins by computing subproblem values (bottom-up). A greedy approach gives an optimal result only for certain coin systems (e.g., canonical systems like typical US coins) because it relies on the greedy-choice property, not on bottom-up computation.
Conclusion: Characterizing the optimal solution structure is shared by both methods; computing values in a bottom-up fashion is specific to dynamic programming.
A video solution is available for this question ā€” log in and enroll to watch it.