So, let’s start with a quote from Confucius.
“Study the past if you would define the future.” — Confucius
The quote let’s us know all we need to know about dynamic programming. We need to remember the results computed for previous small problems to solve bigger newer problems.
There are 2 approaches to dynamic programming usually
- Tabulation — Bottom Up
- Memoization — Top Down
We can take a common problem “Fibonacci Series” to understand the approaches.
The first thing we can try to do is solve it by recursion. So, the recursion solution for Fibonacci is as follows
int fibonacci(int n){
if (n <= 1) return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
Memoization
As we can see above, we have overlapping subproblems, so we don’t need to solve these problems again and again. We can store these solutions, this is memoization. We have a single parameter, so we would need a 1D array.
So how do we apply memoization? We do it with 3 steps.
- Declare the DP array.
- Start adding the solution for computed subproblems into DP array.
- Check if the solutions already exists and use it if it exists.
int fibonacci(int n, int[] dp/* Adding the DP array*/){
if (n <= 1) return n;
if (dp[n] != -1) return dp[n]; //Checking if solution exists and using it
dp[n] = fibonacci(n - 1, dp) + fibonacci(n - 2, dp);//Updating the array if it doesn't exist
return dp[n];
}
So, the time complexity would be O(n). This is because we don’t call the function again for already computed solutions. But, the space complexity would be O(n) + O(n), one for the dp array and another for the extra stack space.
Tabulation
So, now let’s try tabulation. As already highlighted above this is a bottom-up approach. For the current problem, let’s try to rewrite it with tabulation.
int fibonacci(int n){
int[] dp = new int[n + 1];
Arrays.fill(dp, -1);
dp[0] = 0;
dp[1] = 1;
for(int i = 2; i <= n; i++){
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
We calculated the base cases first and started iterating and solving the bigger solutions with previously computed values.
The time complexity is the same, i.e. O(n). The space complexity comes down here because we are not using the stack trace which is O(n).
Space Optimisation on Tabulation
In the above tabulation, we can see that we don’t need to maintain all the previous values. Just the last two solutions would suffice for this problem.
int fibonacci(int n){
int a = 0, b = 1;
for(int i = 2; i <= n; i++){
int cur = a + b;
a = b;
b = cur;
}
return b; //since computing till n
}
Now, we will move on to some more complex problems to apply the above approach in the coming articles.