I think most of the programmers are familiar with recursive code and almost all of us have solved recursive problems like *Fibonacci series* or *Factorial* during our CS courses. We know that if try higher numbers, the code crashes with *StackOverflowError*.

Dynamic programming or DP as it is popularly known is a blessing for many problems requiring either *recursive* or *iterative* algorithms. I am not going to go into the details of DP as such, you can easily find good information about it on Wikipedia or read about it in any one of those excellent tutorials available on the Internet, one such example can be found here on CodeChef.

In short, Dynamic Programming is an approach of solving complex problems by breaking them into several smaller sub-problems, where the sub-problems are overlapping sub-problems. It can make lot of recursive problems much more efficient. Dynamic Programming approach is similar to recursive programming, however in dynamic programming the intermediate results are *cached/stored* for future calls.

If we consider recursive programing for *Fibonacci series*, – computing the n^{th} number depends on the previous n-1 numbers and *each* call results in two recursive calls. Thus, the time complexity is –

T(n) = T(n-1) + T(n-2) = O(2^{n}).

In other words, as we increase the Fibonacci number, the time taken to compute that Fibonacci number increases exponentially!

On the other hand, if we use Dynamic Programming for Fibonacci number, since the earlier results are *cached*, we simply have complexity as –

Time Complexity = O(n)

Extra Space = O(n)

In fact, it is fairly easy to reduce additional space for Fibonacci number by just storing previous two results instead of storing all the previous results.

In plain English, it means that Dynamic Programming can drastically reduce the time taken to compute solutions that require several recursive/iterative calls. As an experiment, I wrote small Java code that computes Fibonacci number using recursion as well as Dynamic Programming. Do watch the results posted below this code to know respective time taken while computing the 50^{th} Fibonacci number. You can try this code with different numbers on your own computer as well and see it for yourself. DP rocks!!! 🙂

```
```public class FiboDyna{
long fibo[] = new long[200];
public long fibonacci(int n){
if (0 == n){
return 0;
}
if(1 == n){
return 1;
}
//return result from cache
if(0 != fibo[n]){
return fibo[n];
}
fibo[n] = fibonacci(n - 1) + fibonacci(n - 2);
return fibo[n];
}
public long fibonacci_rec(int n){
if (0 == n){
return 0;
}
if(1 == n){
return 1;
}
return fibonacci_rec(n - 1) + fibonacci_rec(n - 2);
}
public static void main(String args[]){
FiboDyna fd = new FiboDyna();
long start = System.currentTimeMillis();
System.out.println("Dynamic fibonacci 50 = " + fd.fibonacci(50));
long finish = System.currentTimeMillis();
System.out.println("Time taken for Dynamic Fibbonacci = "
+ (finish - start) + " ms");
start = System.currentTimeMillis();
System.out.println("Recursive fibonacci 50 = " + fd.fibonacci_rec(50));
finish = System.currentTimeMillis();
System.out.println("Time taken for Recursive Fibbonacci = "
+ (finish - start) + " ms");
}
}

I am hoping to use it for some non-trivial, real-life problem whenever I can, and if I manage to do that successfully, I’d definitely post it here!

Cool, nice article Manish.

LikeLike