剑指 offer | 10- I. 斐波那契数列和10- II. 青蛙跳台阶问题

孟君

发布于 2023-02-23 15:49:12

29800

代码可运行

文章被收录于专栏：孟君的编程札记孟君的编程札记

运行总次数：0

代码可运行

题目描述 - 斐波那契那契数

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

题目来源：https://leetcode.cn/problems/fei-bo-na-qi-shu-lie-lcof

斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。

答案需要取模 1e9+7（1000000007），
如计算初始结果为：1000000008，请返回 1

示例 1：

输入：n = 2
输出：1

示例 2：

输入：n = 5
输出：5

提示：

0 <= n <= 100

题目分析

斐波那契（Fibonacci）数列，最容易想到的是递归，比如：

class Solution {
    public int fib(int n) {
        if(n <2) {
            return n;
        }
           return (fib(n-1) + fib(n-2)) % 1000000007;
    }

}

我们可以看到当n=44的时，直接显示【超出时间限制】，显然走不通。需要另想方法。

在我们想其它方法的时候，我们来看看递归方法，n从0到50之间的耗时情况：

public class Solution {

  public int fib(int n) {
    if (n < 2) {
      return n;
    }
    return (fib(n - 1) + fib(n - 2)) % 1000000007;
  }

  public static void main(String[] rags) {
    Test t = new Test();
    for (int i = 0; i < 50; i++) {
      long start = System.currentTimeMillis();
      int result = t.fib(i);
      long costTime = System.currentTimeMillis() - start;
      System.out.println(String.format("fib(%d) = %d, 耗时%d(毫秒)", i, result, costTime));
    }
  }

}

耗时情况，我们可以看出，

递归n=44时，耗时差不多4秒多；n=49的时候，耗时差不多50秒多。

fib(0) = 0, 耗时0(毫秒)
fib(1) = 1, 耗时0(毫秒)
fib(2) = 1, 耗时0(毫秒)
fib(3) = 2, 耗时0(毫秒)
fib(4) = 3, 耗时0(毫秒)
fib(5) = 5, 耗时0(毫秒)
fib(6) = 8, 耗时0(毫秒)
fib(7) = 13, 耗时0(毫秒)
fib(8) = 21, 耗时0(毫秒)
fib(9) = 34, 耗时0(毫秒)
fib(10) = 55, 耗时0(毫秒)
fib(11) = 89, 耗时0(毫秒)
fib(12) = 144, 耗时0(毫秒)
fib(13) = 233, 耗时0(毫秒)
fib(14) = 377, 耗时0(毫秒)
fib(15) = 610, 耗时0(毫秒)
fib(16) = 987, 耗时0(毫秒)
fib(17) = 1597, 耗时1(毫秒)
fib(18) = 2584, 耗时0(毫秒)
fib(19) = 4181, 耗时0(毫秒)
fib(20) = 6765, 耗时1(毫秒)
fib(21) = 10946, 耗时0(毫秒)
fib(22) = 17711, 耗时1(毫秒)
fib(23) = 28657, 耗时0(毫秒)
fib(24) = 46368, 耗时0(毫秒)
fib(25) = 75025, 耗时1(毫秒)
fib(26) = 121393, 耗时1(毫秒)
fib(27) = 196418, 耗时1(毫秒)
fib(28) = 317811, 耗时3(毫秒)
fib(29) = 514229, 耗时4(毫秒)
fib(30) = 832040, 耗时6(毫秒)
fib(31) = 1346269, 耗时8(毫秒)
fib(32) = 2178309, 耗时14(毫秒)
fib(33) = 3524578, 耗时23(毫秒)
fib(34) = 5702887, 耗时39(毫秒)
fib(35) = 9227465, 耗时67(毫秒)
fib(36) = 14930352, 耗时112(毫秒)
fib(37) = 24157817, 耗时187(毫秒)
fib(38) = 39088169, 耗时281(毫秒)
fib(39) = 63245986, 耗时417(毫秒)
fib(40) = 102334155, 耗时671(毫秒)
fib(41) = 165580141, 耗时1088(毫秒)
fib(42) = 267914296, 耗时1760(毫秒)
fib(43) = 433494437, 耗时2826(毫秒)
fib(44) = 701408733, 耗时4542(毫秒)
fib(45) = 134903163, 耗时7357(毫秒)
fib(46) = 836311896, 耗时12350(毫秒)
fib(47) = 971215059, 耗时19366(毫秒)
fib(48) = 807526948, 耗时31308(毫秒)
fib(49) = 778742000, 耗时50677(毫秒)

题斐波那契数使用动态规划dp实现

可以定义一个N+1长度的数组，其中

dp[0] = 0, dp[1] = 1
其余dp[n]= dp[n-1] + dp[n-2]

class Solution {
  public int fib(int n) {
    if (n < 2) {
      return n;
    }
    int[] dp = new int[n+1];
    dp[0] = 0;
    dp[1] = 1;
    for(int i = 2; i<=n; i++ ) {
      dp[i] = (dp[i-1] + dp[i-2]) % 1000000007;
    }
    return dp[n];
  }

}

思考

在上述dp示例中，我们额外定义了一个N+1的数组，把每个计算的结果都存储下来了，其空间复杂度为O(N)。但是，我们不需要中间的每一个计算结果，只要最后一个元素dp[N]。

因为dp[n]= dp[n-1] + dp[n-2]，其实数组我们只要2个元素即可。

class Solution {
  public int fib(int n) {
    if (n < 2) {
      return n;
    }
    int[] dp = new int[2];
    dp[0] = 0;
    dp[1] = 1;
    int sum = 0;
    for(int i = 2; i<=n; i++ ) {
      sum = (dp[0] + dp[1]) % 1000000007;
      dp[0] = dp[1];
      dp[1] = sum;
    }
    return dp[1];
  }

}

这样的话，我们的空间复杂度就改成了O(1)。

再思考一下，数组只有2个元素，我们也可以不用数组，而改成2个变量。

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

}

这样，斐波那契数的写法就差不多完成了。

题目描述 - 青蛙跳台阶问题

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

答案需要取模 1e9+7（1000000007），
如计算初始结果为：1000000008，请返回 1。

题目来源：https://leetcode.cn/problems/qing-wa-tiao-tai-jie-wen-ti-lcof

示例 1：

输入：n = 2
输出：2

示例 2：

输入：n = 7
输出：21

示例 3：

输入：n = 0
输出：1

提示：

0 <= n <= 100

题目分析

由题目描述可知：

输入：n = 0
输出：1

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶

所以，我们来看下规律：

f(0) = 1
f(1) = 1，只有跳1级台阶
f(2) = 2, 可以选择跳2次1级台阶，或者1次2级台阶，所以2种可能
f(3) = f(3-1) [先跳1级台阶)]+ f(3-2) [先跳2级台阶]= f(2) + f(1)
.... ....
f(n) = f(n-1) + f(n-2)

所以，我们发现规律就是

f(0) = 1
f(1) = 1
f(n) = f(n-1) + f(n-2)

我们可以发现，这个规律和斐波那契数的规律类似的，只是f(0) 的值不一样。完全可以采用上述斐波那契数的解决方法。

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

这样，该青蛙跳台阶的问题就一样解决了。

小结

本文针对剑指offer的2道题目" 10- I. 斐波那契数列和10- II. 青蛙跳台阶问题"。斐波那契数列先分析了递归的耗时性，然后使用dp的思想来解决。后面，对青蛙跳台阶问题进行了分析，其和斐波那契数列有共性，可以作为一类问题一起解决。

大家有其它的方法，也可以留言相互交流。

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2022-06-18，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自孟君的编程札记微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度