【14天高效制胜】-第3天-斐波那契数列

红太狼 2022-08-28 12:40 133阅读 0赞

**目录**

1、斐波那契数列

2、爬楼梯

--------------------

# 1、斐波那契数列 #

/**
     * 509. 斐波那契数
     * 斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
     *
     * F(0) = 0，F(1) = 1
     * F(n) = F(n - 1) + F(n - 2)，其中 n > 1
     * 给你 n ，请计算 F(n) 。
     * */

**方法一：递归（耗时）**

//方法一：递归
        public int fib1(int n) {
            if(n == 0) return 0;
            if(n == 1) return 1;
    
            return fib(n-1)+fib(n-2);
        }

**方法二：数组法**

//方法二：数组法
        public int fib(int n){
            if(n == 0) return 0;
            if(n == 1) return 1;
    
            int[] a = new int[n+1];
            a[0] = 0;
            a[1] = 1;
    
            for(int i=2;i<=n;i++){
                a[i] = a[i-1] + a[i-2];
            }
    
            return a[n];
        }

# 2、爬楼梯 #

/**
     * 70. 爬楼梯
     * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
     * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
     * 注意：给定 n 是一个正整数。
     *
     * 输入： 2
     * 输出： 2
     * 解释： 有两种方法可以爬到楼顶。
     * 1.  1 阶 + 1 阶
     * 2.  2 阶
     * */

**方法一：递归法**

//方法一：递归--超时
        //f(n)表示爬n个楼梯的方法数
        public int climbStairs1(int n) {
            if(n == 1) return 1;
            if(n == 2) return 2;
    
            return climbStairs(n-1) + climbStairs(n-2);
        }

**方法二：数组法**

//方法二：数组法
        public int climbStairs(int n){
            if(n <= 0) return 0;
            if(n == 1) return 1;
            if(n == 2) return 2;
            int[] arr = new int[n];
            for(int i=3;i<=n;i++){
                arr[i] = arr[i-1] + arr[i-2];
            }
            return arr[n];
        }