剑指 Offer 10- I. 斐波那契数列

食堂的汤就是斐波那契汤～～～

class Solution {
    public int fib(int n) {
        final int MOD = 1000000007;
        if(n<2){
            return n;
        }
        int p=0,q=0,r=1;
        for(int i=2;i<=n;i++){
            p=q;
            q=r;
            r=(p+q)%MOD;
        }
        return r;
    }
}

爬楼梯也差不多 笑死

class Solution {
    public int climbStairs(int n) {
        int p=0,q=0,r=1;
        for(int i=0;i 
大佬们直接用公式也是我没想到 好强
 
class Solution {
    public int climbStairs(int n) {
        double sqrt_5=Math.sqrt(5);
        double fib_n=Math.pow((1+sqrt_5)/2,1+n)-Math.pow((1-sqrt_5)/2,1+n);
        return (int)(fib_n/sqrt_5);
    }
}