Question

When dynamic programming is applied to a problem, it takes far less time as compared to other methods that don’t take advantage of overlapping subproblems.

(a) True

(b) False

I got this question in a job interview.

Query is from Dynamic Programming topic in portion Dynamic Programming of Data Structures & Algorithms II

Answer 1

Right choice is (a) True

The best explanation: Dynamic programming calculates the value of a subproblem only once, while other methods that don’t take advantage of the overlapping subproblems property may calculate the value of the same subproblem several times. So, dynamic programming saves the time of recalculation and takes far less time as compared to other methods that don’t take advantage of the overlapping subproblems property.