Question

Steps to develop a dynamic programming algorithm: a) Establish a recursive property that gives the solution to an instance of the problem; b) Compute the value of an optimal solution in a bottom-up fashion by solving smaller instances first.

Select one:

True

False

Answer 1

The steps for solving a DP problem is:

a) Establish a recursive property that gives the solution to an instance of the problem;

    (Overlapping Subproblems)

b) Compute the value of an optimal solution in a bottom-up fashion by solving smaller instances first.

    (Optimal Substructure Property)

Hence answer is True