Ch15: Dynamic Programming

Question 1

Dynamic programming applies when the subproblems…

Answer 1

overlap - that is, when they share sub-subproblems

Question 2

A dynamic programming algorithm solves each subproblem…

Answer 2

just once, then saves the answer in a table to avoid recomputing it each time it is needed

Question 3

We typically apply dynamic programming to

Answer 3

optimization problems

Question 4

4 steps of developing a dynamic programming algorithm

Answer 4

1) CHARACTERIZE the structure of an optimal solution 2) Recursively DEFINE the value of an optimal solution 3) COMPUTE the value of an optimal solution, typically in a bottom-up fashion 4) CONSTRUCT an optimal solution from computed information

Question 5

Steps 1-3 of developing a DP algorithm form the basis of…

Answer 5

a DP solution to a problem

Question 6

If we need only the VALUE of an optimal solution and not the solution itself, we can…

Answer 6

omit step 4 (construct an optimal solution)