微信公众号：路人zhang
扫码关注微信公众号

回复“面试手册”，获取本站PDF版

回复“简历”，获取高质量简历模板

回复“加群”，加入程序员交流群

回复“电子书”，获取程序员类电子书

当前位置： 算法 > 剑指offer > 10-2.青蛙跳台阶问题

10-2.青蛙跳台阶问题

题目描述

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

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

示例 1：

输入：n = 2
输出：2

示例 2：

输入：n = 7
输出：21

示例 3：

输入：n = 0
输出：1

提示：

  • 0 <= n <= 100

题解

(动态规划)) O(n)

状态表示：f[i]，表示青蛙跳到第 i 级台阶的所有跳法。

状态计算：按照最后一步是如何跳到第 i 级台阶的分情况讨论：

  1. 从第 i – 1 层跳过来
  2. 从第 i – 2 层跳过来

所以 f[i] = f[i – 1] + f[i – 2]。

边界：

  1. 初始化：f[1] = 1, f[2] = 2，特判：如果 n = 0 则返回 1。
  2. 答案：f[n]。

时间复杂度

O(n)

空间复杂度

O(n)

C++ 代码

class Solution {
public:
    const int mod = 1e9 + 7;

    int numWays(int n) {
        if (!n) return 1;
        if (n <= 2) return n;
        vector<int> f(n + 1);
        f[1] = 1, f[2] = 2;
        for (int i = 3; i <= n; i ++ ) 
            f[i] = (f[i - 1] + f[i - 2]) % mod;
        return f[n];
    }
};

Java 代码

import java.util.Arrays;

class Solution {
    private static final int MOD = 1000000007;

    public int numWays(int n) {
        if (n == 0) {
            return 1;
        }
        if (n <= 2) {
            return n;
        }
        int[] f = new int[n + 1];
        f[1] = 1;
        f[2] = 2;
        for (int i = 3; i <= n; i ++ ) {
            f[i] = (f[i - 1] + f[i - 2]) % MOD;
        }
        return f[n];
    }
}

Python 代码

class Solution:
    def numWays(self, n: int) -> int:
        MOD = 1000000007
        
        if n == 0:
            return 1
        if n <= 2:
            return n
        f = [0] * (n + 1)
        f[1] = 1
        f[2] = 2
        for i in range(3, n + 1):
            f[i] = (f[i - 1] + f[i - 2]) % MOD
        return f[n]

本文由读者提供，Github地址：https://github.com/tonngw

点击面试手册，获取本站面试手册PDF完整版

剑指offer