nth fibonacci number using using dynamic programming

Question

I am able to understand the dynamic programming implementation given HERE.

But I am not clear about the another version given in cracking the coding interview book which I am copy pasting. Can someone please help me understand this, moreover is this not more expensive than the above geeksforgeek dynamic programming implementation.

int[] fib = new int[max];
int fibonacci(int i){
if(i == 0) return 0;
if(i == 1) return 1;
if (fib[i] != 0) return fid[i];
fib[i] = fibonacci(i-1) + fibonacci(i-2);
return fib[i];
}

I suggest you to run this in a debugger to see how the method behaves. After that it should be clear how dynamic programming works for computing the nth fibonacci number. — user2336315
– user2336315, Commented Jan 13, 2015 at 21:43

Niels Billen · Accepted Answer · 2015-01-13 21:45:07Z

1

Basically int[] fib is a cache in which the ith fibonacci number is stored.

This is a great time saver. Otherwise the recursive fibonacci procedure would need to recalculate a lot of values.

E.g.

fib[8] = fibonacci(7) + fibonacci(6)

But then:

fib[7] = fibonacci(6) + fibonacci(5)

As you can see, without caching, the value for fibonacci(6) would be needed to calculated two times.

answered Jan 13, 2015 at 21:45

Niels Billen

2,19913 silver badges12 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

nth fibonacci number using using dynamic programming

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related