【杂题】剑指 Offer 10- II. 青蛙跳台阶问题-跟着帅地玩副业，开拓第二曲线PlayOffer

宁永久会员 2023年3月14日下午5:50

n = 0的预期输出是1

class Solution {
    public int numWays(int n) {
        //动态规划递推，递归的方法时间复杂度太高
        if(n == 0 || n == 1){
            return 1;
        }
        int f1 = 1, f2 = 1;
        int sum = 0;
        for(int i = 2; i <= n; i++){
            sum = (f1 + f2) % 1000000007;
            f1 = f2;
            f2 = sum;
        }
        return sum;
    }
}

0 赞同 0 条回复

lucca 普通 2023年1月17日下午11:42

同理斐波那契

class Solution {
    public int numWays(int n) {
        if (n < 2) return 1;
        int a = 1, b = 1;
        while (n-- > 1) {
            int t = a;
            a = b;
            b += t;
            if (b >= 1000000007) b -= 1000000007;
        }
        return b;
    }
}

0 赞同 0 条回复

努力刷题普通 2022年12月5日上午8:18

时间复杂度：O(n), 空间复杂度：O(1)
class Solution(object):
    def numWays(self, n):
        """
        :type n: int
        :rtype: int
        """
        a, b = 1, 1
        for i in range(n):
            a , b = b, a+b
        return a%1000000007

0 赞同 0 条回复

T 普通 2022年12月3日上午10:02

下面代码

class Solution {
    public int numWays(int n) {
        int a = 1, b = 2, sum;
        for(int i = 1; i < n; i++) {
            sum = (a + b) % 1000000007;
            a = b;
            b = sum;
        }
        return a;
    }
}

0 赞同 0 条回复

symbol 普通 2022年12月3日上午7:59

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

0 赞同 0 条回复

青木普通 2022年12月1日下午9:00

/**
    复习一下昨天的快速幂，由于跳台阶初始值不太一样，因此是直接相加
 */

class Solution {
    public int numWays(int n) {
        int[][] p = {{1, 1}, {1, 0}};
        int[][] res = pow(p, n-1);
        return (res[0][0] + res[0][1])% 1000000007;
    }

    public int[][] pow(int[][] p, int n){
        int[][] ret = {{1, 0}, {0, 1}};
        while(n > 0){
            if((n & 1) == 1){
                ret = multi(ret, p);
            }
            n >>= 1;
            p = multi(p, p);
        }
        return ret;
    }

    public int[][] multi(int[][] a, int[][] b){
        int[][] c = new int[2][2];
        for(int i=0; i<2; i++){
            for(int j=0; j<2; j++){
                c[i][j] = (int) (((long) a[i][0]*b[0][j] + (long) a[i][1]*b[1][j]) % 1000000007);
            }
        }
        return c;
    }   
}

/**
    fibonache昨天优美的写法，这里改了一下初始值，从1开始
 */

class Solution {
    public int numWays(int n) {
        int fn1=1, fn2=1, sum;
        for(int i=0; i<n; i++){
            sum = (fn1 + fn2) % 1000000007;
            fn1 = fn2;
            fn2 = sum;
        }
        return fn1;
    }
}

0 赞同 0 条回复

訁訁訁訁訁普通 2022年12月1日上午12:34

斐波那契同之前

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

优化

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

0 赞同 0 条回复

Mooby 普通 2022年11月30日下午9:06

// 动态规划
// 时间复杂度O(n)，空间复杂度O(1)
class Solution {
    public int numWays(int n) {
        if (n <= 1) {
            return 1;
        }
        int a = 1, b = 1, c = 0;
        for (int i = 2; i <= n; i++) {
            c = (a + b) % 1000000007;
            a = b;
            b = c;
        }
        return c;
    }
}

1 赞同 0 条回复

🚲南下普通 2022年11月30日下午8:35

class Solution {
public:
    int numWays(int n) {
        if(n == 0) return 1;
        else if(n<=2) return n; //与斐波那契类似
        int mod = 1000000007;
        int p=0,q=1,r=2; //1,2,3,5
        for(int i = 2; i<n; i++){
            p = q;
            q = r;
            r = (p+q)%mod;
        }
        return r;
    }
};

0 赞同 0 条回复

西西弗斯的石头永久会员 2022年11月30日下午8:26

时间复杂度O（n），空间复杂度O（1）

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

0 赞同 0 条回复

你有点可爱喔普通 2022年11月30日下午8:26

class Solution {

    static final int val = (int)(1e9+7);
    public int numWays(int n) {
       //dp动态规划法
       if (n <= 1){
           return 1;
       }
       int dp [] = new int[n+2];
       dp[0]  = 1;
       dp[1]  = 1;
       for (int i = 2;i<=n;i++){
           dp[i] = dp[i-1] %val +dp[i-2]%val;
       }
       return dp[n]%val;
    }
}

0 赞同 0 条回复

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

共以下 11 个回答

同理斐波那契

# 回答此问题取消回复

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

共以下 11 个回答

同理斐波那契

# 回答此问题 取消回复

# 回答此问题取消回复