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

Categories:

Tags:

题目描述
思路分析
1. 解法一：动态规划 + 斐波那契递推（推荐）
相似题目

题目描述

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

思路分析

解法一：动态规划 + 斐波那契递推（推荐）

核心思路：

第 n 阶的方案数等于前两阶之和：f(n) = f(n-1) + f(n-2)。

边界：f(0) = 1，f(1) = 1。

用滚动变量替代数组，避免额外空间。

复杂度分析：

时间复杂度：O(n)，其中 n 为台阶数。

空间复杂度：O(1)，仅使用常数额外变量。

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

        int a = 1;
        int b = 1;

        // 斐波那契滚动递推
        for (int i = 2; i <= n; i++) {
            int c = (int) ((a + (long) b) % mod);
            a = b;
            b = c;
        }

        return b;
    }
}

func numWays(n int) int {
    const mod = 1000000007
    if n <= 1 {
        return 1
    }

    a, b := 1, 1

    // 斐波那契滚动递推
    for i := 2; i <= n; i++ {
        c := (a + b) % mod
        a = b
        b = c
    }

    return b
}

相似题目

题目	难度	考察点
70. 爬楼梯	简单	斐波那契
509. 斐波那契数	简单	动态规划
746. 使用最小花费爬楼梯	简单	动态规划
198. 打家劫舍	中等	状态转移
剑指 Offer 10- I. 斐波那契数	简单	递推

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/45943886