//  Data Structures with Java by John R. Hubbard
//  Copyright McGraw-Hill, 2001
//  Example 4.14 on page 81
//  Dynamic Programming Implementation of Fibonacci Function


public class Ex0414
{ public static int fib(int n)
  { if (n<2) return n;
    int[] f = new int[n];
    f[0] = 0;
    f[1] = 1;
    for (int i=2; i<n; i++)    // store the Fibonacci numbers
      f[i] = f[i-1] + f[i-2];
    return f[n-1] + f[n-2];
  }

  public static void main(String[] args)
  { for (int n=0; n<16; n++)
      System.out.println("fib("+n+") = "+fib(n));
  }
}