[每日一题] 第十七题:青蛙跳台阶问题

题目描述

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

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

示例 1:

输入:n = 2
输出:2

示例 2:

输入:n = 7
输出:21

提示:

  • 0 <= n <= 100

题解

方法一:我的做法

本题很容易看出是递归方法来,同斐波那契数列很相似。

这里我列出几个注意事项:

  1. F(0)=1,F(1)=1
  2. F(N) = F(N-1) + F(N-2)
  3. 要把之前的结果保存下来,这样就不会重复计算
  4. 答案一定记得要取模,不然无法通过

代码

class Solution {
    public int numWays(int n) {
        if (n <= 1) {
            return 1;
        }
        int[] nums = new int[n+1];
        nums[0] = 1;
        nums[1] = 1;

        int current = 2;

        while (current <= n) {
            nums[current] = (nums[current-1] + nums[current-2]) % 1000000007;
            current++;
        }

        return nums[n];
    }
}

复杂度

时间复杂度 O(N):计算 f(n) 需循环 n 次,每轮循环内计算操作使用 O(1) 。
空间复杂度 O(N):因为新创建了个 nums 数组,需要额外的 N 个空间

方法二:动态规范

解题思路:

此类求多少种可能性的题目一般都有 递推性质,即 f(n) 和 f(n-1) …… f(1) 之间是有联系的。

  • 设跳上 n 级台阶有 f(n) 种跳法,在所有跳法中,青蛙的最后一步只有两种情况,跳上 1 级或 2 级台阶

    1. 当为 1 级台阶: 剩 n - 1 个台阶,此情况共有 f(n-1) 种跳法;
    2. 当为 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

[每日一题] 第十七题:青蛙跳台阶问题

斐波那契数列的定义是 f(n + 1) = f(n) + f(n - 1) ,生成第 n 项的做法有以下几种:

  1. 递归法:
    原理: 把 f(n) 问题的计算拆分成 f(n−1) 和 f(n−2) 两个子问题的计算,并递归,以 f(0) 和 f(1) 为终止条件。
    缺点: 大量重复的递归计算,例如 f(n) 和 f(n−1) 两者向下递归都需要计算 f(n−2) 的值。
  2. 记忆化递归法:
    原理: 在递归法的基础上,新建一个长度为 n 的数组,用于在递归时存储 f(0) 至 f(n) 的数字值,重复遇到某数字时则直接从数组取用,避免了重复的递归计算。
    缺点: 记忆化存储的数组需要使用 O(N) 的额外空间。
  3. 动态规划:
    原理: 以斐波那契数列性质 f(n+1)=f(n)+f(n−1) 为转移方程。
    从计算效率、空间复杂度上看,动态规划是本题的最佳解法。

动态规划解析:

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

空间复杂度优化:

若新建长度为 n 的 dp 列表,则空间复杂度为 O(N)。

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

循环求余法:

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

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

复杂度:

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

解法来源

作者:jyd
链接:leetcode-cn.com/problems/qing-wa-t...
来源:力扣(LeetCode)

来源

来源:力扣(LeetCode)
链接:leetcode-cn.com/problems/qing-wa-t...
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

本作品采用《CC 协议》,转载必须注明作者和本文链接
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

请勿发布不友善或者负能量的内容。与人为善,比聪明更重要!