c++ - iterative solution as dynamic programming -

wikipedia says dynamic programming :

in mathematics, computer science, economics, , bioinformatics, dynamic programming method solving complex problem breaking down collection of simpler subproblems. applicable problems exhibiting properties of overlapping subproblems , optimal substructure. when applicable, method takes far less time other methods don't take advantage of subproblem overlap (like depth-first search).

and introduction algorithms (cormen) , have learnt dynamic programming method applied solve repeating computations have already been computed once. in layman's terms ,

if you're going compute again , again , better store somewhere.

applying on fibonacci write algorithm follows :

arr[3] = {1,1,1} //first 2 index computation , last 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 1         return res;     } }  

while believe algorithm follows example of dynamic programming reduces 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 2 separate calls @ each recursive step else return fibb(n-1) + fibb(n-2) many computations repeated.

an iterative solution :

int fibonacciiterative(int n) {     if (n == 0) return 0;     if (n == 1) return 1;      int prevprev = 0;     int prev = 1;     int result = 0;      (int = 2; <= n; i++)     {         result = prev + prevprev;         prevprev = prev;         prev = result;     }     return result; } 

so question , iterative solution fibonacci problem classified dynamic programming?

my reasoning disagreement , iterative solution dosen't exhibits overlapping subproblems such recursive solution exhibiting. in iterative solution , there no redundant , repetitive computations being made , shouldn't included in dynamic programming.

relevant articles : optimal substructure , overlapping subproblems , dynamic programming.

yes. that's special case of bottom dynamic programming. you're allowed discard table entries know never use again, in case of fibonacci means need keep 2 entries, , can forget ever table , use 2 named variables. so, ends looking different, simple. structure of algorithm still dp. overlapping subproblems aren't there still there, because use every result twice (once when it's in prev, again when it's in prevprev), except in end. of course there no redundant computations made, that's idea of dp - remove redundant computation reuse.

there general "plan of attack" problems allow dynamic programming, namely

• state problem recursively
• (prove dp can applied)
• identify ordering of sub-problems such topologically sorted (so computing solution relies on trivial solutions , previously-computed solutions, not on future ones)
• fill table iteratively in order, if there nice order. maybe keep top down structure if order annoying.

in case of fibonacci, happened order trivial (that's not particularly uncommon, makes if we're "not doing special"), , dependencies never go more 2 places, part of table has remembered previous 2 cells. applying that, well-known iterative algorithm. doesn't mean it's not dp anymore, means dp extremely successful.

as properties (optimal substructure, overlapping subproblems), they're properties of problem, don't go away no matter how decide solve it. can still see them in iterative algorithm, pointed out in first paragraph.