Dynamic Programming

Question

Is this Fibonacci code considered dynamic programming since it stores previous results?

This is the code:
https://code.sololearn.com/cA178A24a258

Thanks in advance.

Answer 1

I would say that your approach is just an iterative one. On this wikipedia article, there are two algorithms for calculating Fibonacci.
https://en.m.wikipedia.org/wiki/Dynamic_programming
I think you are losing out on the benefit of both of them.
If we define f(n) = f(n-1) + f(n-2)
This would be a recursive, top-down approach. This is where memoization would be useful.
The other way is bottom-up, so you start with the first two elements and calculate the next one from those, but in this case you don't need to remember each element, just the last two.

The essence of dynamic programming is to break down a complicated problem into subproblems that can be solved recursively. Read more here:
https://www.freecodecamp.org/news/demystifying-dynamic-programming-3efafb8d4296/

Answer 2

Mohamed Khatma

In above program function fib() has array size is

int i, v[n];

At end it's returns

return v[n];

It is a operation like array out of bound. It should calculate till n-1 or array size needs to be v[n+1].

DHANANJAY PATEL