【斐波那契数(509-java)】

斐波那契数(509-java)

斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给你 n ，请计算 F(n) 。

示例 1：

输入：2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1

public class LC115_509_fib {
    //递归
    public static int fib(int n) {
        if (n == 1 || n == 2) {
            return 1;
        }
        return fib(n - 1) + fib(n - 2);
    }

    //通讯录--自顶而下
    public static int fib1111(int n) {
        if (n < 1) {
            return 0;
        }
        int[] dp = new int[n + 1];
        return help(dp, n);
    }

    private static int help(int[] dp, int n) {
        if (n == 1 || n == 2) {
            return 1;
        }
        if (dp[n] != 0) {
            return dp[n];
        }
        return help(dp, n - 1) + help(dp, n - 2);
    }

    //动态规划
    public static int fib222(int n) {
        int[] dp = new int[n + 1];
        //dp[0]默认为0
        dp[1] = dp[2] = 1;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

    //动态规划剪枝
    public static int fib2223333(int n) {
        if (n < 1) {
            return 0;
        }
        if (n == 1 || n == 2) {
            return 1;
        }
        int pre = 1;//前一项总和
        int curr = 1;//当前总和
        for (int i = 3; i <= n; i++) {
            int sum = pre + curr;
            pre = curr;
            curr = sum;
        }
        return curr;
    }

    public static void main(String[] args) {
        System.out.println(fib2223333(5));
    }
    
}