Before going to problems, let us understand how Dynamic Programming works through examples –
Fibonacci Series –
In the Fibonacci series, the current number is the sum of the previous two numbers. The Fibonacci series is defined as follows:
Fib(n) = 0, for n = 0; = 1, for n = 1 = Fib(n-1) + Fib(n-2), for n>1
The recursive implementation can be given as –
int RecursiveFibonacci(int n) {
if(n == 0 || n == 1) return n;
return RecursiveFibonacci(n-1) + RecursiveFibonacci(n-2);
}
How does memorization help?
Calling fib(5) produces a call tree that calls the function on the same value many times:
fib(5) fib(4) + fib(3) (fib(3) + fib(2)) + (fib(2) + fib(1)) ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1)) (((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
In the above example, fib(2) was calculated three times (overlapping of subproblems). If n is big, then many more values of fib (sub-problems) are recalculated, which leads to an exponential time algorithm. Instead of solving the same sub-problems again and again we can store the previously calculated values and reduce the complexity. Memoization works like this: Start with a recursive function and add a table that maps the function’s parameter values to the results computed by the function. Then if this function is called twice with the same parameters, we simply look up the answer in the table.
Improving: Now, we see how DP reduces this problem’s complexity from exponential to polynomial. As discussed earlier, there are two ways of doing this. One approach is bottom-up: these methods start with lower values of input and keep building the solutions for higher values.
int fib[n]
int fib(int n){
if(n == 0 || n == 1) return 1;
fib[0] = 1;
fib[1] = 1;
for(int i=2;i<n;i++){
fib[i] = fib[i-1] + fib[i-2];
return fib[n-1];
}
The other approach is top-down. In this method, we preserve the recursive calls and use the values if they are already computed. The implementation for this is given as:
int fib[n];
int fibonacci(int n){
if(n == 1 || n == 2) return 1;
if(fib[n]!=0) return fib[n];
return fib[n] = fibonacci(n-1) + fibonacci(n-2);
}
Note: For all problems, it may not be possible to find both top-down and bottom-up programming solutions. Both versions of the Fibonacci series implementations clearly reduce the problem complexity to O(n).
This is because if a value is already computed then we are not calling the subproblems again. Instead, we are directly taking its value from the table.
Time Complexity: O(n). Space Complexity: O(n), for the table.
Further Improving: One more observation from the Fibonacci series is: The current value is the sum of the previous two calculations only.
This indicates that we don’t have to store all the previous values.
Instead, if we store just the last two values, we can calculate the current value. The implementation for this is given below –
int fibonacci(int n){
int a = 0,b = 1,sum,i;
for(int i=0;i<n;i++){
sum = a + b;
a = b;
b = sum;
}
return sum;
}
Time Complexity: O(n).
Space Complexity: O(1).
Note: This method may not be applicable (available) for all problems.
Observations
While solving the problems using DP, try to figure out the following:
- See how the problems are defined in terms of subproblems recursively.
- See if we can use some table [memoization] to avoid repeated calculations.
