Consider the problem of computing the
*generalized Fibonacci numbers* .
The generalized Fibonacci numbers of order are given by

Notice that the ``normal'' Fibonacci numbers considered in Section are the same as the generalized Fibonacci numbers of order 2.

If we write a recursive function that implements directly Equation , we get an algorithm with exponential running time. For example, in Section it is shown that the time to compute the second-order Fibonacci numbers is .

The problem with the direct recursive implementation is that it does far more work than is needed because it solves the same subproblem many times. For example, to compute it is necessary to compute both and . However, in computing it is also necessary to compute , and so on.

An alternative to the top-down recursive implementation is to do the calculation from the bottom up. In order to do this we compute the series of sequences

Notice that we can compute from the information contained in simply by using Equation .

Program defines the function `Fibonacci`
which takes two integer arguments *n* and *k*
and computes the Fibonacci number of order *k*
using the approach described above.
This algorithm uses an array to represent
the series of sequences .
As each subsequent Fibonacci number is computed
it is added to the end of the array.

**Program:** Dynamic Programming Example--Computing Generalized Fibonacci Numbers

The worst-case running time of the `Fibonacci` routine
given in Program is a function of both *n* and *k*:

Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.