简单动态规划

题目链接-来源：力扣（LeetCode）

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：

输入：n = 2
输出：2

思路：

记 f(i) 为青蛙跳到第 i 级台阶的跳法数。由于青蛙可以从 i - 1 或者 i - 2 级台阶跳上来，所以 f(i) = f(i - 1) + f(i - 2)。
其实这就是斐波那契数列的递推式，从前一题可以得到启发，用一个队列来迭代地存储这个过程。

时间复杂度：O(n)
空间复杂度：O(1)

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int numWays(int n) {
        int mod = 1000000007;
        Queue<Integer> q = new LinkedList<>();
        q.offer(1);
        q.offer(1);
        for (int i = 0; i <= n; i++) {
            if (i == n) {
                return q.poll();
            }
            q.offer((q.poll() + q.peek()) % mod);
        }
        return 1;
    }
}