Per the lecture, dynamic programming differs from divide and conquer because
AD&C uses recursion; DP never uses recursion
BD&C is faster than DP on every problem
CD&C sub-problems are independent; DP overlap
DDP requires sorted input; D&C does not
Answer & Solution
Correct answer: C. D&C sub-problems are independent; DP overlap
Both split into sub-problems. D&C's sub-problems are independent (merge sort's two halves share no work), so memoising doesn't help. DP's sub-problems repeat (Fibonacci, LCS, knapsack), so memoising collapses exponential repeated work into polynomial. DP also uses recursion (top-down) or iteration (bottom-up); sorted input is unrelated.
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