As usual lets start with the general definition of dynamic programming.
“In computer science DP is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions – ideally, using a memory-based data structure”
The general definition talks about solving a bigger problem by splitting it into simpler subproblems. The key here is to solve each subproblem only once. If the same problem set occurs again, that should not be computed. Then how are we going to deal with that subproblem ? Memoization is the solution.
What is memoization ?
“Memoization is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.”
Let understand the concept in a very simple way.
Jack and Jill are very good friends. (Don’t ask me who is Jack in the below picture 🙂 )
Jack is a sharp mind, however Jill faces tough time when it comes to solving problems. One day Jill wanted to test Jack’s mind and he asked him.
“Hey Jack, people keep saying you are good at problem solving. Lets test your skills today.Ready ?”
Jack replied : “Sure, shoot the problem “.
Jill : Ok, but you have to answer quickly.
Jack : Sure! Go ahead.
Jill draws a matrix of 0’s and 1’s on a piece of paper and asks Jack to calculate the longest set of adjacent 1’s.
Jack looks at the matrix takes some time and then tells him the answer.
Jill smiles and says, “that was easy enough” and extends the matrix by drawing more cells on the paper. “Now tell me the answer” asks Jill, laughing out loud. Again Jack was able to answer quickly.
Jill kept extending the matrix on the paper and challenging Jack.
Each time Jack would answer correctly and Jill would get angry. This continued quite for a while.
In the whole process, Jack used a piece of paper to write something without showing Jill, what he was actually writing.
Jill finally accepted defeat and asked him to explain how he was able to answer these questions quickly ? and what was Jack writing down on the piece of paper after answering every question.
Jack smiled and replied, it was simple. After each question I was writing down my answer for the previous matrix, and using it for calculating the next problem.
So, basically Jack was memoizing the results of the previous subproblem on a piece of paper, which helped him solve bigger problem. Unknowingly he was using Dynamic programming approach.
Now, lets apply similar in the classic fibonacci series problem.
Below is a typical recursive solution for fibonacci problem.
int fibonacci(long n) {
if (n == 0) {
return 0;
} else if (n == 1) {
return 1;
} else {
return fibonacci(n - 1) + fibonacci(n - 2);// Recursive call to fibonacci function with smaller subset.
}
}
Above code is correct and will give perfect results. But wait, there is a big issue with this solution. Lets take a look at the below tree which shows the execution of the above fibonacci function.
Take a closer look and you will observe that there are some function calls which are called multiple times. for example f(2), f(1),f(3),f(4). Which means that same computation is performed multiple times.As a result for larger inputs the function will take a lot of time to execute and will crash for even larger inputs.
So can you figure out what could be the solution to this problem, based on what Jack did ?
Take 2 mins to think and you will come up the solution.
I am sure you came up with a solution called “Memoization”. Well done!!
So let’s take a look at the improvised code.
int fibonacci(long n) {
long fibValue = 0;
if (n == 0) {
return 0;
} else if (n == 1) {
return 1;
} else if (fibArray[(int) n] != 0) {
return fibArray[(int) n]; //Computation is saved here. result is directly returned from the memory.
} else {
fibValue = fibonacci(n - 1) + fibonacci(n - 2); // Recursive function calls.
fibArray[(int) n] = fibValue; // Memoize the solution, before we lose it.
return fibValue;
}
Hope this article was helpful. Thanks for visiting.
Cheers,
Kaivalya Apte
