面试题10.3：变态跳台阶

题目描述

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

知识点

递归，循环

Qiang的思路

这道题算是面试题10.2的升级版，10.2说的是青蛙一次只能跳一个或者是两个，现在牛逼了，多少都能跳（你咋不上天呢）。

对于上一个问题，我们维护了两个整数空间用来保存上一时刻和上上时刻的状态数，推广过来，我们现在只需要维护一个n个整数空间的状态数组就能够解决该问题了。

# -*- coding:utf-8 -*-
class Solution:
    def jumpFloorII(self, number):
        # write code here
        count = [1,1]
        for i in range(2,number+1):
            count.append(0)
            for j in range(0,i):
                count[-1]+=count[j]
        return count[number]

我这个想法完全继承自上一题的思路，还是非常简单的。

Book中的思路

这道题在书中没有占很多的篇幅，仅有短短的三行字，但是他给出了一个结论：

关于该结论的证明可以通过如下的两个小式子得到：

这个结论恰恰是该问题的结果，有时我们在做题时可能就陷入了一个误区，用这方法用那方法，可能通过分析，问题刚刚可以转化为一个简单的数学问题，然后答案呼之欲出。

# -*- coding:utf-8 -*-
class Solution:
    def jumpFloorII(self, number):
        # write code here
        if number==0:
            return 1
        return 1<<(number-1)

代码实现起来是非常简单的。

作者原创，如需转载及其他问题请邮箱联系：lwqiang_chn@163.com。
个人网站：https://www.myqiang.top。