Okay, consider two ways of dynamic programming:
Top-down: Using this technique you avoid intense processing (such as an exponential recursive time recursive function) by saving known values so that you don't have to recalculate them.
Bottom-up: With this method, instead of saving known values, you precompute them
Using the Fibonacci example, here is the bad version:
Code:
int fib ( int i )
{
if ( i < 1 )
return 0;
if ( i == 1 )
return 1;
return fib ( i - 1 ) + fib ( i - 2 );
}
Using a Bottom-up method, the exponential time of the fib function was cut down to linear simply by simply by computing the first N numbers and storing them in a global array, the function avoids recomputing values.
Code:
int pre[45];
int fib ( int i )
{
int t;
if ( pre[i] != 0 )
return pre[i];
else if ( i == 0 )
t = 0;
else if ( i == 1 )
t = 1;
else if ( i > 1 )
t = fib ( i - 1 ) + fib ( i - 2 );
return pre[i] = t;
}
-Prelude