Dynamic programming Introduction

                              Dynamic Programming Introduction                                          

Dynamic Programming is mainly an optimization over plain recursion. Wherever we see a recursive solution that has repeated calls for same inputs, we can optimize it using Dynamic Programming.For example, if we write simple recursive solution for Fibonacci Numbers, we get exponential time complexity and if we optimize it by storing solutions of sub problems, time complexity reduces to linear.

Fibonacci Number using recursion and dynamic programming

Let us start understand it with an example.  Let us take example as fib(4) For fib(4), 

• fib(0) will called twice, 
• fib(1) will be called thrice , 
• fib(2) will be called twice,
• fib(3) will be called once and
• fib(4) will be called once.

 In dynamic programming we storing the values of fib(2) in array f[2] So that we need not to call again and again.Therefore time complexity reduces to linear.

Fibonacci series using recursion