Dynamic Programming (DP) is an algorithmic technique for solving an optimization problem by breaking it down into simpler subproblems.
Characteristics
Characteristics of a problem that can be solved using dynamic programming. – Overlapping Subproblems – If any problem has overlapping sub-problems and in finding its solution involves solving the same subproblem multiple times.
- Optimal Substructure Property
- A problem has optimal substructure property if its overall optimal solution can be constructed from the optimal solutions of its subproblems
Methods
-
Top-down with Memoization
- In this approach, we try to solve the bigger problem by recursively finding the solution to smaller sub-problems. Whenever we solve a sub-problem, we cache its result so that we don’t end up solving it repeatedly if it’s called multiple times. Instead, we can just return the saved result. This technique of storing the results of already solved subproblems is called Memoization.
-
Bottom-up with Tabulation
- Tabulation is the opposite of the top-down approach and avoids recursion.
- In this approach, we solve the problem “bottom-up” (i.e. by solving all the related sub-problems first). This is typically done by filling up an n-dimensional table. Based on the results in the table, the solution to the top/original problem is then computed.