What are overlapping subproblems?
A problem has overlapping subproblems if finding its solution involves solving the same subproblem multiple times.
What is dynamic programming?
Dynamic programming is an algorithms design technique which solves problems by combining the solutions to subproblems. It applies when subproblems overlap.
Which kinds of problems does dynamic programming typically apply to?
OPTIMIZATION PROBLEMS. These problems have many possible solutions, and each has a value, and we wish to find a solution with the optimal value.
What are the steps that need to be followed when developing dynamic programming algorithm
- Characterize the structure of an optimal solution.
- Recursively define the value of an optimal solution.
- Compute the value of an optimal solution, typically in a bottom-up fashion.
- Construct an optimal solution from computed information (If only the value is needed this step can be ommited).
What are two ways to implement a dynamic programming approach?
- Top-down with memoization
- Bottom-up
What is the trade-off that dynamic programming makes?
It uses additional memory to save computation time.
What are some typical dynamic programming problems?
- Rod cutting
- Matrix chain multiplication
