How to solve a dynamic programming problem?
What is dynamic programming?
Dynamic programming is an optimization technique developed by Richard Bellman in the 1950s. Basically, dynamic programming is an optimization over the normal recursion. In the case of recursion, repeated calls are made for the same sub-problem, but we can optimize this problem with the help of dynamic programming. The idea behind using dynamic programming is that we store the results of sub-problems so that we do not need to re-compute the sub-problem whenever required. This reduces the time complexities from exponential time to linear time.
Below is the code of Recursion with exponential time.
Below is the code of dynamic programming with linear time.
Techniques to solve a dynamic programming problem.
To solve any dynamic programming problem, we can use the FAST method.
Here, FAST stands for:
- ‘F’ stands for Find the recursive solution: Whenever we find any DP problem, we have to find the recursive solution.
- ‘A’ stands for Analyse the solution: Once we find the recursive solution then we have to analyse the solution and look for the overlapping problems.
- ‘S’ stands for Save the results for future use: Once we find the overlapping problems, we store the solutions of these sub-problems. To store the solutions, we use the n-dimensional array for caching purpose.
The above three steps are used for the top-down approach if we use ‘F’, ‘A’ and ‘S’, which means that we are achieving the Top-down approach. Since it is not purely because we are using the recursive technique.
- ‘T’ stands for Tweak the solution to make it more powerful by eliminating recursion overhead which is known as a Bottom-up approach. Here we remove the recursion technique and use the iterative approach to achieve the same results, so it’s a pure approach. Recursion is always an overhead as there are chances of getting a stack overflow error, so we should use the bottom-up approach to avoid this problem.
Above are the four steps to solve a complex problem.
Problem Statement: Write an efficient program to find the nth Fibonacci number?
As we know that Fibonacci series looks like:
0, 1, 1, 2, 3, 5, 8, 13, 21,…
First, we find the recursive solution,
The below is the code of the above recursive solution:
The above recursive solution is also the solution for the above problem but the time complexity in this case is O(2n). So, dynamic programming is used to reduce the time complexity from the exponential time to the linear time.
Second step is to Analyse the solution
Suppose we want to calculate the fib(4).
Fib(4)= fib(3) + fib(2)
Fib(3) = fib(2) + fib(1)
Fib(2) = fib(1) + fib(0)
As we can observe in the above figure that fib(2) is calculated two times while fib(1) is calculated three times. So, here overlapping problem occurs. In this step, we have analysed the solution.
Third step is to save the result.
The process of saving the result is known as memoization. In this step, we will follow the same approach, i.e., recursive approach but with a small different that we have used the cache to store the solutions so that it can be re-used whenever required.
Below is the code of memoization.
In the above code, we have used a cache array of size n+1. If cache[n] is not equal to zero then we return the result from the cache else we will calculate the value of cache and then return the cache. The technique that we have used here is top-down approach as it follows the recursive approach. Here, we always look for the cache so cache will be populated on the demand basis. Suppose we want to calculate the fib(4), first we look into cache, and if the value is not in the cache then the value is calculated and stored in the cache.
Visual representation of the above code is:
Fourth step is to Tweak the solution
In this step, we will remove the recursion completely and make it an iterative approach. So, this technique is known as a bottom-up approach.
In the above code, we have followed the bottom-up approach. We have declared a cache array of size n+1. The base cases are cache and cache with their values 0 and 1 respectively. In the above code, we have removed the recursion completely. We have used an iterative approach. We have defined a for loop in which we populate the cache with the values from the index i=2 to n, and from the cache, we will return the result. Suppose we want to calculate f(4), first we will calculate f(2), then we will calculate f(3) and finally, we we calculate the value of f(4). Here we are going from down to up so this approach is known as a bottom-up approach.
We can visualize this approach diagrammatically:
As we can observe in the above figure that we are populating the cache from bottom to up so it is known as bottom-up approach. This approach is much more efficient than the previous one as it is not using recursion but both the approaches have the same time and space complexity, i.e., O(n).
In this case, we have used the FAST method to obtain the optimal solution. The above is the optimal solution that we have got so far but this is not the purely an optimal solution.
The above solution is the efficient solution as we do not use the cache.