Algorithms Dynamic programming suggest change

Fibonacci Number

Bottom up approach for printing the nth Fibonacci number using Dynamic Programming.

Recursive Tree

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(0)

Overlapping Sub-problems

Here fib(0),fib(1) and fib(3) are the overlapping sub-problems.fib(0) is getting repeated 3 times, fib(1) is getting repeated 5 times and fib(3) is getting repeated 2 times.

Implementation

public int fib(int n){
        int f[] = new int[n+1];
        f[0]=0;f[1]=1;
        for(int i=2;i<=n;i++){
            f[i]=f[i-1]+f[i-2];
        }
        return f[n];
    }

Time Complexity

O(n)

Feedback about page:

Feedback:
Optional: your email if you want me to get back to you:



Table Of Contents