Dynamic Programming
Dynamic Programming is an algorithmic method for solving optimization problems by breaking them(a problem or problems) into smaller subproblems.
It is an algorithm paradigm. Or simply put a type or class of algorithms just like Greedy, and divide & conquer.
It is very handy in solving certain types of problems. And the aim of this section is to try and help us learn how to identify these kinds of problems.
I will do so by examining the 4 steps for arriving at the optimal solution for a given DP problem. However, let's start by exploring the characteristics of dynamic programming problems
- Optimal substructure
- Overlapping subproblems
Four steps to find an optimal solution for a DP problem
1) Recurrence relation
A relation that repeats itself
2) Top-Down approach
Come up with a solution from a global level/top level by breaking it into smaller ones and finding a solution to each one of them until we arrive at the global one.
3) Bottom-up
First, build solutions to the smaller subproblems and then you build a global one from all of these.
4) Optimize
Find ways to optimize the bottom-up solution in terms of memory or runtime performance so that we have a more efficient solution.
In the first 2 steps, we identify if the problem can solved in a dynamic programming approach or not by establishing if the problem has:-
1) Optimal substructure
2) Overlapping subproblems
What is an optimization Problem?
Optimization problems have many forms, but today, I will discuss the 3 types that are very frequent and occur almost every other time.
Enumeration
Consider the following example of an enumeration problem: You want to climb n steps. At any step, you either climb 1, 2, or 3 steps. How many different ways can you take to climb the n stairs?
Looking at the above example, enumeration problems generally ask you to count the number of ways that you can do something, just like the number of times you climb the stairs.
Minimization/Maximization Problems
Let's consider a scenario with an array A[1 ... n] of stock prices on different days. We want to buy and sell on 2 different days. Find the maximum amount of money we can make.
These kinds of problems are all about minimizing the cost that you have to pay or they simply maximize the amount you make.
Yes/ No Problems
A sample scenario asks if you can form $35 dollars given p 6 pennies, q 20 pennies, and r quarters.
How do you Solve DP problems?
The key approach is breaking a problem into smaller subproblems.
We then solve these sub-problems (smaller problems) individually, and then we combine their solutions to form the solution of the larger problems.