Solutions to the problems from the course: https://www.youtube.com/channel/UClnwNEngsXoIp_tgJ2jZWfw
Introduction
- Optimal Substructure
- Overlapping subproblems
To solve a structure we can leverage the substructure.
Easy example is fibonaci. To solve fibonaci(n) we just need to use fibonaci(n-1) + fibonaci(n-2).
Dynamic programming can solve these two types of problems:
- Combinatoric problems: answer how many
- Optimization probelm: maximize/minimize
- Define objective function
- Identifying the base cases
- Recurrence relation
- Order of computation
- Location of the answer