斐波納契數

使用動態程式設計列印第 n 個 Fibonacci 數的自下而上方法。

遞迴樹

                         fib(5)   
                     /             \     
               fib(4)                fib(3)   
             /      \                /     \
         fib(3)      fib(2)         fib(2)    fib(1)
        /     \        /    \       /    \  
  fib(2)   fib(1)  fib(1) fib(0) fib(1) fib(0)
  /    \
fib(1) fib(0)

重疊子問題

這裡 fib(0)，fib(1)和 fib(3) 是重疊的子問題 .fib(0) 重複 3 次，fib(1) 重複 5 次，fib(3) 重複 2 次倍。

履行

public int fib(int n){
        int f[] = new int[n+1];
        f[0]=0;f[1]=1;
        for(int i=2;i<=n;i++){
            f[i]=f[i-1]+f[i-2];
        }
        return f[n];
    }

時間複雜性

上）