Leetcode青蛙跳台阶

1.题目

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

答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。

示例 1:

输入:n = 2
输出:2

示例 2:

输入:n = 7
输出:21

提示:

  • 0 <= n <= 100

2.解答

1.无脑递归

这也是递归的一个入门级题目,虽然思路很简单,但是直接暴力解决的话不能提交成功,

image

原因是这个过程进行了太多的重复计算,当台阶总数比较多的时候根本顶不住

class Solution {
    public int numWays(int n) {
        if(n == 0)  return 1;
        if(n <= 2)  return n;
        return numWays(n-1) + numWays(n-2);
    }
}

2.保存计算过的值

这种方法中,我们将计算过的值直接保存到HashMap中,key为阶数,value为当前阶数的跳法,当后面需要使用前面计算过的值时候,直接从HashMap中get出来,有一点动态规划的意思

代码:

class Solution {
    //使用HashMap保存计算过的值,其中key为台阶数,value为跳法 
    //为避免递归函数中重复床创建HashMap,直接定义为类变量
    private static HashMap<Integer,Integer> hashmap = new HashMap<>();   
    public int numWays(int n) {
        if(n == 0)  return 1;       
        if(!hashmap.containsKey(n)){
            if(n <= 2)
                hashmap.put(n,n);
            else
                hashmap.put(n,numWays(n-1)+numWays(n-2));
        }
        //对大值进行取模运算
        return hashmap.get(n) % 1000000007;
       
    }
  
}

3.动态规划

动态规划解析:

  • 状态定义: 设 dpd**p 为一维数组,其中 dp[i]d**p[i] 的值代表 斐波那契数列第 $i$ 个数字
  • 转移方程: dp[i + 1] = dp[i] + dp[i - 1]d**p[i+1]=d**p[i]+d**p[i−1] ,即对应数列定义 f(n + 1) = f(n) + f(n - 1)f(n+1)=f(n)+f(n−1) ;
  • 初始状态: dp[0] = 1d**p[0]=1, dp[1] = 1d**p[1]=1 ,即初始化前两个数字;
  • 返回值: dp[n]d**p[n] ,即斐波那契数列的第 nn 个数字。

空间复杂度优化:

若新建长度为 nn 的 dpd**p 列表,则空间复杂度为 O(N)O(N) 。

  • 由于 dpd**p 列表第 ii 项只与第 i-1i−1 和第 i-2i−2 项有关,因此只需要初始化三个整形变量 sum, a, b ,利用辅助变量 sumsum 使 a, ba,b 两数字交替前进即可 (具体实现见代码)
  • 因为节省了 dpd**p 列表空间,因此空间复杂度降至 O(1)O(1) 。

循环求余法:

大数越界: 随着 nn 增大, f(n)f(n) 会超过 Int32 甚至 Int64 的取值范围,导致最终的返回值错误。

  • 求余运算规则: 设正整数 x, y, px,y,p ,求余符号为 \odot⊙ ,则有 (x + y) \odot p = (x \odot p + y \odot p) \odot p(x+y)⊙p=(xp+yp)⊙p
  • 解析: 根据以上规则,可推出 f(n) \odot p = [f(n-1) \odot p + f(n-2) \odot p] \odot pf(n)⊙p=[f(n−1)⊙p+f(n−2)⊙p]⊙p ,从而可以在循环过程中每次计算 sum = a + b \odot 1000000007sum=a+b⊙1000000007 ,此操作与最终返回前取余等价。

图解基于 Java 代码绘制,Python 由于语言特性可以省去 sumsum 辅助变量和大数越界处理。

img

8 / 12

复杂度分析:

  • 时间复杂度 O(N)*O*(*N*) : 计算 f(n)f(n) 需循环 nn 次,每轮循环内计算操作使用 O(1)O(1) 。
  • 空间复杂度 O(1)*O*(1) : 几个标志变量使用常数大小
class Solution {
    public int numWays(int n) {
        int a = 1, b = 1, sum;
        for(int i = 0; i < n; i++){
            sum = (a + b) % 1000000007;
            a = b;
            b = sum;
        }
        return a;
    }
}