chap patterns of algorithms if we could eliminate this redundancythe cost would be greatly reduced the approach that we will use can also improve any algorithm that spends most of its time recomputing common subproblems one way to accomplish this goal is to keep table of valuesand first check the table to see if the computation can be avoided here is straightforward example of doing so int fibrt(int nintvalues/assume values has at least slotsand all /slots are initialized to if ( < return /base case if (values[ ! return values[ ]values[nfibr( - valuesfibr( - values)return values[ ]this version of the algorithm will not compute value more than onceso its cost should be linear of coursewe didn' actually need to use table storing all of the valuessince future computations do not need access to all prior values insteadwe could build the value by working from and up to rather than backwards from down to and going up from the bottom we only need to store the previous two values of the functionas is done by our iterative version long fibi(int nlong pastprevcurrpast prev curr /curr holds fib(ifor (int = <=ni++/compute next value past prevprev curr/past holds fib( - curr past prev/prev holds fib( - return currthis issue of recomputing subproblems comes up frequently in many casesarbitrary subproblems (or at least wide variety of subproblemsmight need to be recomputedso that storing subresults in fixed number of variables will not work thusthere are many times where storing table of subresults can be useful this approach to designing an algorithm that works by storing table of results for subproblems is called dynamic programming the name is somewhat arcanebecause it doesn' bear much obvious similarity to the process that is taking place when storing subproblems in table howeverit comes originally from the field of