Algorithm Problem Solving — Memoization
Having the basic understanding of Recursion is necessary before jumping onto Memoization technique used in algorithms, please take a look at the following problem and solve the problem by drawing out the recursion tree.
Problem Statement
You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb 1 or 2 step(s). In how many distinct ways you can climb to the top?
The problem statement is the same in the linked post, but this time we are going to add the optimization.
I have went ahead and completed the recursion tree from the last problem, I have highlighted the parts where the calculation is repeated. The observation to make here is once we are at a certain stair #, there are only so many distinct ways of getting to the top.
Example:
Case 1: If you have two steps left to climb, you can take 1+1 or 2 steps. So that makes it two distinct ways to do it.
Case 2: If you have 1 step left to climb there is only one way to do it and that is by taking 1 step(If you take two steps you will reach beyond the designated top spot).
So essentially the pattern to observe is,
2 steps left to climb => 2 ways of doing it.
1 step left to climb => 1 way of doing it.
3 steps left to climb => 3 ways of doing it 3 => (1,1,1), (1,2), (2,1).
So if we can cache in these results and look it up later we need not do this calculation repeatedly(Pretty cool huh!), the data structure to the rescue is HashMap. Map data structures are used to store the key, value references, this is one of the most important data structure in the field of Computer Science and you will use it on a daily basis in the field of Software Engineering.
To visualize how the look up table is going to look like,
Implementation:
The same optimization can be applied for the fibonacci problem described in the previous post, try applying a cache layer to the problem and enjoy the faster run time.
Talking about run time we can mathematically prove the optimization by measuring the run-time.
Run-time analysis without optimization:
We can measure the time it takes for recursion with a simple formula, Number of branches at each step O(2^n) where two represents the number of branches(decisions at each step of the recursion) and n represents the number of times we do this.
In the above example, we can find that the 2 is the number of ways at each particular step and we continue doing this operation from n times(Until we reach the top).
Run-time analysis with optimization:
We added an optimization where we cut down the time from O(2^n) to O(n) where n represents the size of the recursion tree since we are caching the results.
Bonus point:
We can solve this problem using dynamic programming as well, I am going to leave it up to you on how you can formulate this into a DP problem.
My next blog post is going to be about the Trie Data Structure which is little advanced but absolutely fun to walkthrough.