Dynamic programming using javascript — dp
Programming is all about problem-solving and the thing that we care the most in our programs is that it just takes the least time to run and it consumes the least memory. So literally we need proper optimization of our programs.
There are a ton of ways to optimize a program, optimization can be defined as reducing the time and space complexity.
So, now comes the word “Dynamic Programming” don't think its something like rocket science. It is just a way to optimize some problems and yes you cant use dynamic programming everywhere. Here the question comes which types of problems we can solve using dynamic programming. The answer is pretty simple “Any problem which can be divided into subproblems of the same type for example like a Fibonacci series which we usually solve using recursion”.
Let me explain it more clearly, So dynamic programming can be thought of a recursively optimized problem. What that,
Let's see it by the example of a Fibonacci series problem and how dynamic programming can solve it more efficiently.
Fibonacci series: — 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144………………….
The classic way we solve it by using recursion but there is Gotch if you try to find the Fibonacci of no greater than 25 your program will crash.
Let me show you.
You can clearly see that our function ran 242785 times that is horrible.
If you want to crash your editor try with input 80 or more It will be fun.
So now this is a gotcha so how we can resolve it and here comes the dynamic programming in rescue. Let me first show you with a simple example that how dynamic programming works.
Now time to introduce the new term “Memoization”. Don't mess up its not a jargon it is simple. Memoization is caching or vice-versa. Basically what we do is when we calculate something we store it somewhere like here we are using javascript we will use an object to store the calculated value and if we again need to calculate the same value we will just return it from the object.
So how it will help us Lets see with an example.
In the above picture, we are calculating the same thing five times and suppose the function takes a long time to run so if we run the function five times and each time it will take a long time to calculate it will be very bad. So, what is the escape here like we are calculating the same thing we can save this value somewhere and if we are asked to calculate the same thing again we will just return it.
each second time we are calculating the same thing we are just returning it from the stored value each input are just calculated once and in the next call we are just returning the pre-calculated value.
Now, how can we use this knowledge to solve the Fibonacci problem?
Have a look at this picture
for calculating Fibonacci of five we have to calculate Fibonacci of 1 five times two-three times. The reason for showing this is that we are doing a lot of useless calculation. If you will calculate the time-complexity we will get O(2^n) that is horrible and can't be used practically.
Now we have a way to solve this problem that is by Dynamic Programming.
In Javascript to make it possible we have to use Closure don't feel bad if you don't know closure, it is a bit tricky but really useful. So closure is basically a property of function in javascript through which it can access data out of its scope. I will link you to some good resources for learning Closure in Js.
Let see the program for the problem using dynamic programming.
We can see that in this case where we are using dynamic programming to solve this our function just ran 59 times let check it with greater inputs.
That's the beauty.
Now You can use this caching to solve a complex problem with less time complexity. We have just reduced the time complexity from O(2^n) to O(n).
How cool it is.
Dynamic Programming is a little tough to get in the beginning. You can use any language to solve your problem using Dynamic Programming.
Feel free to ask any question????
