// 思路：动态规划
class Solution {
    public int Fibonacci(int n) {
        if(n == 0){
            return 0;
        }
        int[] f = new int[n + 1];
        f[0] = 0;
        f[1] = 1;
        if(n >= 2){
            for(int i = 2; i < n+1; i++){
                f[i] = f[i-1] + f[i-2];
            }
        }
        return f[n];
    }
}