斐波纳契数

使用动态编程打印第 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];
    }

时间复杂性

上）