Per the lecture, dynamic programming applies to problems that have
Aoptimal substructure AND overlapping sub-problems
Bneither property; DP works on every problem
Cthe greedy-choice property and a sorted input
Dnon-deterministic finite automata in the recurrence
Answer & Solution
Correct answer: A. optimal substructure AND overlapping sub-problems
Both properties are needed. Optimal substructure: the best whole solution is built from best sub-problem solutions. Overlapping sub-problems: the same sub-problem repeats in naive recursion, which is what makes memoisation pay off. Without overlap, plain recursion (or D&C) suffices; without optimal substructure, neither DP nor greedy work.
Related questions
An NP-hard problem differs from an NP-complete one because NP-hard problemsThe first problem proved to be NP-complete wasA problem X is NP-complete if and only ifWhy does theoretical computer science draw the line at 'polynomial-time' for tractability?Which set inclusion is established (i.e., proven, not open)?The class NP is the set of decision problems for whichFloyd-Warshall detects the presence of a negative cycle byTopological sort is well-defined for