【杂题】剑指 Offer 10- II. 青蛙跳台阶问题

本问题对应课程链接：剑指offer刷题第三期

要求：
1、请打卡你的解题代码，如果能简单说一下思路则简单说一下思路。
2、给出你代码所用的时间复杂度和空间复杂度

shuaidi

更新于 3 年前 86 11

共以下 11 个回答

九号球普通 2023年12月3日下午8:40

“`java
class Solution {
public int trainWays(int num) {
//dp[i]表示有i个格子时的跳跃方式，则dp[i] = dp[i – 1] + dp[i – 2];
//dp[1] = 1,dp[2] = 2
if (num == 0) {
return 1;
}
if (num <= 2) { return num; } int[] dp = new int[num + 1]; dp[1] = 1; dp[2] = 2; for (int i = 3; i <= num; i++){ dp[i] = (dp[i-1] + dp[i-2])%1000000007; } return dp[num]; } }

0 赞同 0 条回复

登录以回复

张开怀普通 2023年7月24日下午8:18

class Solution {
public:
    int numWays(int n) {
        if (n <= 1) {
            return 1;
        }

        int a = 1;
        int b = 1;
        int c = 0;

        for (int i = 2; i <= n; i++) {
            c = (a + b) % 1000000007;
            a = b;
            b = c;
        }

        return c;
    }
};

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

0 赞同 0 条回复

yxy 普通 2023年7月24日下午3:08

时间O(n)

class Solution {
public:
    const int M = 1e9+7;
    int numWays(int n) {
        if(n==0) return 1;
        if(n==1) return 1;
        if(n==2) return 2;
        int a = 1, b = 1, c = 0;
        for(int i=2;i<=n;i++)
        {
            c = (a+b)%M;
            a = b;
            b = c;
        }
        return c;
    }
};

0 赞同 0 条回复

小吕普通 2023年7月24日下午2:34

c++实现
int numWays(int n) {
int MOD = 1000000007;
if(n<2)return 1;
int p= 0,q= 1,r= 2;
for(int i = 3;i<=n;i++)
{
p=q;
q=r;
r=(p+q)%MOD;
}
return r;
}

0 赞同 0 条回复

登录以回复

mpweixin用户永久会员 2023年7月24日上午11:51

class Solution {
//时间O(n) 空间O(n)
    public int numWays(int n) {
        if(n < 2){
            return 1;
        }
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for( int i = 2;i <= n;i++){
            dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007;
        }

        return dp[n];

    }
}

0 赞同 0 条回复

Vow the vow。普通 2023年7月24日上午11:12

跟斐波那契数列是一个意思。

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

0 赞同 0 条回复

哈哈哈哈开开心心普通 2023年7月24日上午2:01

class Solution:
    def climbStairs(self, n: int) -> int:
        a, b = 1, 1

        for i in range(2, n + 1):
            tmp = b
            b += a
            a = tmp

        return b

基本

0 赞同 0 条回复

花老爷普通 2023年7月23日下午5:28

动态规划
时间：O(n)
空间：O(1)

class Solution {
    public int numWays(int n) {
        int f = 1, s = 1, cur = 1;
        for (int i = 2; i <= n; i++) {
            cur = (f + s) % 1000000007;
            f = s;
            s = cur;
        }
        return cur;
    }
}

0 赞同 0 条回复

怀瑾永久会员 2023年7月23日下午3:57

C++实现

“`C++
public int numWays(int n) {
if(n <= 1) return 1; int a = 1; int b = 1; int c = 0; for(int i = 2; i <= n; i++) { c = (a + b) % 1000000007; a = b; b = c; } return c; } ```

0 赞同 0 条回复

登录以回复

Yodl. 普通 2023年7月23日下午3:51

//动态规划
class Solution {
public:
    int numWays(int n) {
        if(n==1||n==0)
        {
            return 1;
        }
        if(n==2)
        {
            return 2;
        }
        int dp[n+1];
        dp[1]=1;
        dp[2]=2;
        for(int i=3;i<=n;i++)
        {
            dp[i]=(dp[i-1]+dp[i-2])%1000000007;
        }
        return dp[n];
    }
};

0 赞同 0 条回复

Ming 普通 2023年7月23日下午3:44

思路和斐波那契数列一样，初始值看案例

public int numWays(int n) {
        if(n <= 1) return 1;
        int a = 1;
        int b = 1;
        int c = 0;
        for(int i = 2; i <= n; i++) {
            c = (a + b) % 1000000007;
            a = b;
            b = c;
        }
        return c;
    }

0 赞同 0 条回复

# 回答此问题取消回复

后才能回答

【杂题】剑指 Offer 10- II. 青蛙跳台阶问题

共以下 11 个回答

# 回答此问题 取消回复

# 回答此问题取消回复