Dynamic Programming

Question 1

What are overlapping subproblems?

Answer 1

A problem has overlapping subproblems if finding its solution involves solving the same subproblem multiple times.

Question 2

What is dynamic programming?

Answer 2

Dynamic programming is an algorithms design technique which solves problems by combining the solutions to subproblems. It applies when subproblems overlap.

Question 3

Which kinds of problems does dynamic programming typically apply to?

Answer 3

OPTIMIZATION PROBLEMS. These problems have many possible solutions, and each has a value, and we wish to find a solution with the optimal value.

Question 4

What are the steps that need to be followed when developing 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 (If only the value is needed this step can be ommited).

Question 5

What are two ways to implement a dynamic programming approach?

Answer 5

• Top-down with memoization

- Bottom-up

Question 6

What is the trade-off that dynamic programming makes?

Answer 6

It uses additional memory to save computation time.

Question 7

What are some typical dynamic programming problems?

Answer 7

• Rod cutting

- Matrix chain multiplication