.png)
What are subproblems?
Dynamic programming is often used to solve problems which can broken down into smaller problems. It is very efficient in solving these types of problems.
Today we will learn how to use dynamic programming in problem solving. We first need to learn about two things:
- states
- memoization
Building states and transition between states
Building a state is the first thing you should do when encountered with a dynamic programming (DP) problem.
Take the classic knapsack problem for example,, what would be our state?