剑指 Offer 10- II: 青蛙跳台阶问题

[songyy5517]

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：

输入：n = 2
输出：2

示例 2：

输入：n = 7
输出：21

示例 3：

输入：n = 0
输出：1

提示：0 <= n <= 100

分析 这道题需要我们求n级台阶的跳法数。由题可知，当前台阶的跳法可以由之前台阶跳法数推导而来，因此将不同台阶的跳法数看成是不同的状态，我们可以使用动态规划来解决。

[songyy5517]

思路：动态规划

1. 异常处理；

2. 定义相关变量：

   • f_1, f_2 分别表示当前状态-1步和-2步的方案数；
   • res记录当前结果。

3. 自下而上计算，并更新各个状态；

• 当只有 0级或 1级台阶时，跳法只有1种（f(0) = f(1) = 1）

• 当有2级或2级以上的台阶时，跳法为： （1）第一次跳1级，剩下的跳法为 f(n-1); （2）第一次跳2级，剩下的跳法为 f(n-2); 因此，总跳法为 f(n) = f(n-1) + f(n-2)

4. 返回最终结果。

复杂度分析

• 时间复杂度： $O(N)$ ，计算状态一共需要 $N - 2$ 次循环，使用 $O(N)$ 大小的时间；
• 空间复杂度： $O(1)$ ，额外定义了常数大小的变量。

[songyy5517]

import java.util.*;

public class Solution {

    public int Fibonacci (int n) {
        // write code here
        // 思路：DP，自下而上计算各个状态
        // 1. 异常处理
        if (n < 3)
            return 1;

        // 2. DP
        int f_1 = 1, f_2 = 1;
        int res = 1;

        for (int i = 3; i <= n; i++){
            res = f_1 + f_2;
            f_2 = f_1;
            f_1 = res;
        }

        return res;
    }
}

[songyy5517]

2022-05-24 2023/1/13 2024/3/26