简介:本文主要记录了 变态跳台阶问题 的推导过程

题目描述

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

解题思路

问题转换

这个问题我们可以转换思路,将其转换成求树的节点个数的题目。

假设存在一棵树,它的根节点是N,它的子节点从左往右依次为 n-1, n-2, … 直到0。同理,根节点子节点的子节点也遵循这样的规律,0节点没有子节点。请问在这棵树中,0节点一共有多少个? 根节点为3的树如下图所示:

答案推导

如上所示,我们已经将问题转换成了求树中0节点的个数,根据树的递归定义,我们可以得到如下的定义:

  • $f(1) = 1$
  • $f(n) = f(n-1) + f(n-2) + … + f(1) + 1$
  • $f(n-1) = \space \space \space \space \space \space \space \space \space \space \space f(n-2) + … + f(1) + 1$

令$f(n) - f(n-1)$,可得:$f(n) = 2 * f(n-1)$。

根据$f(1) = 1$和$f(n) = 2 * f(n-1)$,我们最终可以得到,$f(n) = 2^{n-1}$。

最终答案

有了上面的推导过程,最终的编程实现很简单,我们只需要返回$2^{n-1}$即可,答案如下:

1
2
3
4
5
6
7
8
9
#include <cmath>

class Solution {
public:
    int jumpFloorII(int number) {
        return pow(2, number - 1);
    }
};