Questions and Answers
What is a key requirement for applying Dynamic Programming?
Problem divided into overlapping sub-problems
What is a distinguishing factor of the dynamic programming algorithm compared to a brute force recursive algorithm?
Runs typically in quadratic time
What is the principle that dynamic programming relies on for solving problems?
Principle of optimality, recursive relation between smaller and larger problems