题目链接

牛客网

题目描述

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

解题思路

动态规划

设f[i] 表示 当前跳道第 i 个台阶的方法数。那么f[n]就是所求答案。
假设现在已经跳到了第 n 个台阶，那么前一步可以从哪些台阶到达呢？
如果上一步跳 1 步到达第 n 个台阶，说明上一步在第 n-1 个台阶。已知跳到第n-1个台阶的方法数为f[n-1]
如果上一步跳 2 步到达第 n 个台阶，说明上一步在第 n-2 个台阶。已知跳到第n-2个台阶的方法数为f[n-2]
。。。
如果上一步跳 n 步到达第 n 个台阶，说明上一步在第 0 个台阶。已知跳到 第0个台阶的方法数为f[0]
那么总的方法数就是所有可能的和。也就是f[n] = f[n-1] + f[n-2] + … + f[0]
显然初始条件f[0] = f[1] = 1
所以我们就可以先求f[2]，然后f[3]…f[n-1]， 最后f[n]

  1. class Solution {
  2. public:
  3.     int jumpFloorII(int number) {
  4.         if(number<2)
  5.             return number;
  6.         vector<int> f(number+1,0);
  7.         f[0]=f[1]=1;
  8.         for(int i=2;i<=number;i++)
  9.             for(int j=0;j<i;j++)
  10.             {
  11.                 f[i]=f[i]+f[j];
  12.             }
  13.         return f[number];
  14.     }
  15. };
  • 时间复杂度：O(n^2)
  • 空间复杂度：O(n)

    数学推导

    跳上 n-1 级台阶，可以从 n-2 级跳 1 级上去，也可以从 n-3 级跳 2 级上去…，那么
    10.4 变态跳台阶 - 图2
    同样，跳上 n 级台阶，可以从 n-1 级跳 1 级上去，也可以从 n-2 级跳 2 级上去… ，那么
    10.4 变态跳台阶 - 图3
    综上可得
    10.4 变态跳台阶 - 图4
    即
    10.4 变态跳台阶 - 图5
    所以 f(n) 是一个等比数列
    class Solution {
public:
  int jumpFloorII(int number) {
      if(number<3)
          return number;
      return pow(2, number-1);
  }
};
    时间复杂度：O(n)
    空间复杂度：O(1)