15 Dynamic Programming

Question 1

How is dynamic programming similar to divide and conquer?

Answer 1

Both solve complex problems by breaking them into smaller, easier to solve subproblems.

Question 2

How is dynamic programming different to divide and conquer?

Answer 2

The subproblems solved by dynamic programming are not independent, and are repeatedly encountered in different contexts.

Question 3

What is Dynamic Programming effective for?

Answer 3

Problems where the same subproblem needs to be solved repeatedly.

Question 4

Every dynamic programming algorithm uses:

Answer 4

A table that has one entry for each subproblem.

Question 5

The development of a dynamic programming has 3 Key components:

Answer 5

1. The recurrence relation (for defining the value of an optimal solution)
2. The tabular computation (for computing the value of an optimal solution)
3. The traceback (for extracting an optimal solution).

Question 6

Longest common String Running Time

Answer 6

O(m*n)