青蛙跳台阶问题

---

题目：

题解：

1、动态规划

• 解题思路：

  • 设跳上 n 级台阶有 f(n) 种跳法。在所有跳法中，青蛙的最后一步只有两种情况： 跳上 1 级或 2 级台阶。
    • 当为 1 级台阶： 剩 n-1 个台阶，此情况共有 f(n-1) 种跳法；
    • 当为 2 级台阶： 剩 n-2 个台阶，此情况共有 f(n-2) 种跳法。
  • f(n) 为以上两种情况之和，即 f(n)=f(n-1)+f(n-2)，以上递推性质为斐波那契数列。本题可转化为 求斐波那契数列第 n 项的值 ，与 斐波那契数列 - 轩辕&小站 等价，唯一的不同在于起始数字不同。
    • 青蛙跳台阶问题： f(0)=1 , f(1)=1 , f(2)=2 ；
    • 斐波那契数列问题： f(0)=0 , f(1)=1 , f(2)=1 。
    • 

• 复杂度分析：

  • 时间复杂度 O(N) ： 计算 f(n) 需循环 n 次，每轮循环内计算操作使用 O(1)。
  • 空间复杂度 O(1) ： 几个标志变量使用常数大小的额外空间。

• 代码：

  public class Solution {
      public int numWays(int n) {
          int a = 1;
          int b = 2;
          // 记录每次的a+b，避免重复计算
          int sum = 0;
          while (n-- > 0) {
              sum = (a+b) % 1000000007;
              a = b;
              b = sum;
          }
          return a;
      }
  }