Memoization : An Essential Tool in Dynamic Programming
The concept along with some examples
Introduction:
Dynamic programming is an optimized and usually recursion-based approach to problem-solving where the intermediate results are stored to reduce repetitive computations and thus reducing the time complexity of an algorithm. Dynamic programming can be used when a problem can be divided into subproblems.
The process of storing the result of expensive computations to be re-used is called memoization. It plays a significant part in reducing time complexity by improving an algorithm’s performance.
The Nth Fibonacci Number is the poster child of problems that can be solved efficiently using memoization. The Fibonacci sequence is the sequence where the nth number is the sum of its last two predecessors — 0, 1, 1, 2, 3, 5, 8, 11, and so on.
Here is the code for a standard recursion based solution in C++:
The first two numbers are 0 and 1. This can be considered as a base case for this algorithm. The image below represents the function calls made by func() to calculate the nth Fibonacci number:
This algorithm is functional, but it has an exponential time complexity, which is undesirable. It can be observed that some of the branches in the tree are identical. Memoization can be used to store the values that have been calculated once. If the value of func(n) has been calculated once, it can be reused to reduce the amount of computational work that has to be done.
Here is the code to calculate the Nth Fibonacci Number using memoization in C++:
The logic of the program has not been modified. The only difference is that the calculated values are being stored to avoid redoing some of the calculations. The function call for this code will be much smaller than it was without memoization. The “nodes” in white will not be called because the function values for those particular numbers have already been calculated:
The time and space complexity for this memoized algorithm will be O(n). There is a significant improvement in the time complexity of this algorithm because of memoization and it is more drastic and obvious as the input size grows.
Let’s go through a more complex example to understand how to properly apply memoization to a suitable problem.
Problem statement :
You are given a set of integers, both negative and non-negative, and you can apply any one of the three operations over each element as you iterate over the input array — You can either add, subtract or skip over an element to obtain the maximum value, but you cannot use the same operation consecutively.
Sample input : [ -2, 4, 0, 5, 2, -3, -6, 8 ]
Sample output : 23
Order of operations to obtain maximum value:
This problem is very different from the Fibonacci number problem as it does not require recursion, so it might be difficult to imagine how memoization should be applied. However, some things to be observed are:
- The potential optimal sequence can have 3 starting points — that is, either of the three operations can be applied over the first element. After that, every element will have two branches. So we should create a vectorfor each starting point that stores the updated value after an operation has been applied to an element. We can also initialise the first elements for each vector:
The first element for the add vector is the first element of the input array, as it is added to 0. Similarly, the first element of the sub vector is -1 times the first input element, as it is to be subtracted from 0. The first element for the skp vector is simply 0, as there is no change to be made.
2. Only one of two operations can be applied to the elements that follow, as the operation used on the previous element cannot be applied again. For example, if the previous element was added to the value, the current element can either be subtracted from the value or, it can be skipped.
3. If we wish to apply the addition operation, the previous element must have either been subtracted from the value, or it must have been skipped. There are two possibilities in this case, so we must choose the one that results in the greater value. The image below illustrates this point :
The add vector stores the sum of the current value and the greater value from the arrays where the previous element was skipped and subtracted. A similar approach is used for each starting point and for each element, hence the for loop.
After iterating over the input array, we return the greatest value from the final element of the three vectors. The code for the function in C++ :
This function also runs in linear time and takes up linear space, as opposed to a brute force solution that has an exponential time complexity because this problem can also branch out with every element that is given as input.
These are just two problems that can be efficiently solved using memoization. There are lots of unique problems that can be done with the help of memoization, but it cannot be applied everywhere. It requires the problem to have similar subproblems. It is only helpful when it is used to avoid recalculation of complex or lots of computations. Memoization arrays are not necessarily one dimensional. It can have multiple dimensions if the problem demands it.
This is blog does not cover all there is to memoization and is meant to function solely as a primer for the uninitiated. Some resources for further learning have been appended.
Some links for further reading:
> Understanding Memoization In JavaScript ― Scotch.io
> Memoization (1D, 2D and 3D) — GeeksforGeeks
Some practice problems to reinforce the concept:
> Solve Memoization and DP Questions | Functional Programming | HackerRank
