Beta. Content is under active construction and has not been peer-reviewed. Report errors on
GitHub
.
Disclaimer
Theorem
Path
Curriculum
Paths
Demos
Diagnostic
Search
Quiz Hub
/
Dynamic Programming
Dynamic Programming
1 questions
Difficulty 7-7
View topic
Advanced
0 / 1
1 advanced
Adapts to your performance
1 / 1
advanced (7/10)
conceptual
Dynamic programming requires two properties: optimal substructure and overlapping subproblems. Which problem lacks optimal substructure and therefore cannot be solved with standard DP?
Hide and think first
A.
Longest simple path in a general graph (without negative edges)
B.
Shortest path in a graph with non-negative edges (Dijkstra)
C.
The knapsack problem
D.
Matrix chain multiplication
Submit Answer