Wikipedia says this about dynamic programming :
In mathematics, computer science, economics, and bioinformatics, dynamic programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems. It is applicable to problems exhibiting the properties of overlapping subproblems and optimal substructure. When applicable, the method takes far less time than other methods that don't take advantage of the subproblem overlap (like depth-first search).
and also from Introduction to Algorithms (Cormen) , I have learnt that dynamic programming is a method applied to solve repeating computations that have already been computed once. In layman's terms ,
if you're going to compute something again and again , better store it somewhere.
Applying this on Fibonacci I could write its algorithm as follows :
arr[3] = {1,1,1} //first two index for computation , last to keep track
fibbDyn(n){
if(n>=1 || a[2]>n ) return n; // return on base conditions
else {
res = arr[0] + fibbDyn(n-1);
arr[0]=arr[1];
arr[1]=res;
arr[2]+=1; // increment value by 1
return res;
}
}
While I believe this algorithm follows the example of dynamic programming as it reduces the extra computations being done in original recursive fibbonaci version :
fibb(n){
if (n>=1)return n;
else return fibb(n-1) + fibb(n-2);
}
as here due to two separate calls at each recursive step else return fibb(n-1) + fibb(n-2) many computations are repeated.
an iterative solution will probably look like :
int FibonacciIterative(int n)
{
if (n == 0) return 0;
if (n == 1) return 1;
int prevPrev = 0;
int prev = 1;
int result = 0;
for (int i = 2; i <= n; i++)
{
result = prev + prevPrev;
prevPrev = prev;
prev = result;
}
return result;
}
So my question is , will an iterative solution to Fibonacci problem be classified as dynamic programming?
My reasoning for a disagreement is that , an iterative solution dosen't exhibits Overlapping subproblems such as an recursive solution is exhibiting. In an iterative solution , there are no redundant and repetitive computations being made , so it shouldn't be included in dynamic programming.
relevant articles : optimal substructure , overlapping subproblems , dynamic programming.
