Dynamic Programming

Question 1

What is dynamic programming?

Answer 1

Dynamic programming solves problems by combining the solutions to subproblems

Question 2

What is the difference between DP and divide-and-conquer?

Answer 2

D&C algorithms partition the problem into disjoint subproblems, solve the subproblems recursively, and then combine their solutions to solve the original problem.
In contrast, DP applies when the subproblems overlap - that is, when subproblems share subsubproblems.

In this context, a D&C algorithm does more work than necessary, repeatedly solving the common subsubproblems.

Question 3

What are the steps do develop a DP algorithm?

Answer 3

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 4

What are key characteristics a optimization problem must have in order for DP to apply?

Answer 4

1. Optimal substructure

2. Overlapping subproblems

Question 5

What does ‘optimal substructure’ mean in the context of DP?

Answer 5

A problem exhibits optimal substructure if an optimal solution to the problem contains within it optimal solutions to subproblems.

Question 6

What does ‘overlapping subproblems’ mean in the context of DP?

Answer 6

When a recursive algorithm revisits the same problem repeatedly, we say that the optimization problem has overlapping subproblems. DP algorithms typically take advantage of overlapping subproblems by solving each subproblem once and then storing the solution in a table where it can be looked up when needed, using constant time per lookup.