Remember when I told you how that we where goint to learn about how we can design algorithms efficiently form the start. Then dont worry that we got you covered!
First of all let’s state what a sub problem is. So we have this big problem that we want to solve, and we look for similar and smaller solutions to that initial problem. Most of the times the first set of sub problems are still hard to solve themselves, so we create sub problems from those sub problems. We continue on unitl we have such a simple sub problem that is solved. Then those bottom sub problem can join to solve the more intermidiate subproblems, until we reach the top problem we wanted to solve, and wemagaged to solve the initial problem. All problems that can be solved this way aare said to have optimal substructure.
Does that style of programming remind you of anything? YES: Recursion! If we can identify the optimal substructure of an algorithm, we can then apply dynamic programming to solve an algorithms. Let us try a quick example:
5! = 5*4*3*2*1 or 5! = 5*4! .... n! = n*(n-1)!
To calculate 5!, we need to know 4! first, and to calculate 4! we need to know 3! and so on. The bug problem is calculate 5!, the intermidiate solutions would be 4! or 3! etc, the base sub problem is 1!, which is defined as 1! = 1. Therefore we divide 5! into 5*4! and divide it to 5*4*3! and so on, until we reach 1. Then we go back up, and start multiplying the known values, until we reach 5! the top of the subproblem. This type of design is called bottom-up calculation.
This is great! We can implement this for any natural number! Let’s say just after that calculation we want to calculate another factorial number, like 9! Then we have to calculate 8!, 7!, ... , and so on first. The way our algorithm is defined, we have to do all that work again, including the previously calculated 5! Calculating 5! over and over again can be very time consuming!
Now we introduce you memoization. Memoization is nothing else than storing different values of a sub problem on a table (ex. arrays), so instead of calculating the whole sub problem again, we check the table to see if we have previous records of a solution of a sub-problem. So now When we calculate 7! after 5!, we only have to calculate 6! and 7! This greatly improves the running time of an algorithm!
In summary, dynamic programming can be described as finding the optimal substructure of a problem, building a bottom up recursion solution for each sub problem, and storing the solution of each sub-subproblem on a memoization table (memo-table for short).
Hoped you liked today’s Lesson. Next time we wil be covering greedy algorithms. Leo Out!
blakekathryn
areudirty
andulkaphoto
turnnoffyourmind
baratheonpilled
amandla
gummygunk