题解 | #斐波那契数列#

public class Solution {
    //递归实现
    /*public int Fibonacci(int n) {
        if(n==1||n==2){
            return 1;
        }
        return Fibonacci(n-1) + Fibonacci(n-2);

    }*/
    //非递归实现
    /*public int Fibonacci(int n) {
        if(n==1||n==2){
            return 1;
        }
        int a = 1;
        int b = 1;
        int temp;
        for(int i = 3; i <= n; i++){
            temp = a;
            a = b;
            b = b + temp;
        }
        return b;

    }*/
    //动态规划实现
    public int Fibonacci(int n) {
        if(n==1||n==2) return 1;
        int[] arr = new int[n];
        arr[0] = 1;
        arr[1] = 1;
        for(int i = 2; i < n; i++){
            arr[i] = arr[i-1] + arr[i-2];
        }
        return arr[n-1];
    }
}