青蛙跳台阶问题

题目链接：https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/

image.png

题目解析
和斐波那契数列类似，使用动态规划 F(N) = F(N-1) + F(N-2),其中F(0)和F(1) == 0

public int numWays(int n) {        
         // F(N) = F(N-1) + F(N-2)

        //f0 = 1
        //f1 = 1
        //f2 = 1+1
        if (n <2){
            return  1;
        }
        final int MOD = 1000000007;
        //fn2 对应F(n-2)
        //fn1 对应F(n-1)
        //fn 对应F(n)
        int fn2 =1 ,fn1 = 1, fn = 0;
        for(int i = 2; i <= n; i++){
            fn = (fn2 + fn1) % MOD;
            fn2 = fn1;
            fn1 = fn;
        }
        return fn;
    }

复杂度分析
空间复杂度: O(1)。
时间复杂度: O(N)。