Java Reference
In-Depth Information
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 a table of values, and first check the
table to see if the computation can be avoided. Here is a straightforward example
of doing so.
intFibrt(intn,int * Values){
//AssumeValueshasatleastnslots,andall
//slotsareinitializedto0
if(n<=1)return1; //Basecase
if(Values[n]!=0)
Values[n]=Fibr(n-1,Values)+Fibr(n-2,Values);
returnValues[n];
}
This version of the algorithm will not compute a value more than once, so its
cost should be linear. Of course, we didn't actually need to use a table storing all of
the values, since future computations do not need access to all prior subproblems.
Instead, we could build the value by working from 0 and 1 up to n rather than
backwards from n down to 0 and 1. Going up from the bottom we only need to
store the previous two values of the function, as is done by our iterative version.
/ ** Iterativelygenerateandreturnthen'thFibonacci
number * /
staticlongfibi(intn){
//fibr(91)isthelargestvaluethatfitsinalong
assert(n>0)&&(n<=91):"noutofrange";
longcurr,prev,past;
if((n==1)||(n==2))return1;
curr=prev=1; //currholdscurrentFibvalue
for(inti=3;i<=n;i++){//Computenextvalue
past=prev; //pastholdsfibi(i-2)
prev=curr; //prevholdsfibi(i-1)
curr=past+prev; //currnowholdsfibi(i)
}
returncurr;
}
Recomputing of subproblems comes up in many algorithms. It is not so com-
mon that we can store only a few prior results as we did for Fibi . Thus, there are
many times where storing a complete table of subresults will be useful.
This approach to designing an algorithm that works by storing a table of results
for subproblems is called dynamic programming. The name is somewhat arcane,
because it doesn't bear much obvious similarity to the process that is taking place
when storing subproblems in a table. However, it comes originally from the field of
dynamic control systems, which got its start before what we think of as computer
programming. The act of storing precomputed values in a table for later reuse is
referred to as “programming” in that field.
Search WWH ::




Custom Search