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