剑指Offer （Python）变态跳台阶

推荐在线编程平台

牛客网在线编程

题目描述

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

分析

这是“跳台阶”的一个变形，我们可以用相同的思路来计算：

1. 令f(n)表示跳n级台阶的跳法
2. 假设青蛙第一次跳了一级台阶，那么剩下n-1级台阶有f(n-1)种跳法； 如果第一次跳了两级台阶，则剩下n-2级台阶有f(n-2)种跳法。
3. 以此类推，可以得到： f(n) = f(0) + f(1) + f(2) + ... + f(n-2) + f(n-1) 通过这个公式，我们可以知道: f(n-1) = f(0) + f(1) + f(2) + ... + f(n-2)
4. 所以f(n) = 2 * f(n-1) 说明跳n级台阶的跳法就是跳上前一级跳法的两倍，所以我们可以通过递归来计算。

代码

# -*- coding:utf-8 -*-
class Solution:

    def jumpFloorII(self, number):

        if number == 0:
            return 0
        elif number == 1:
            return 1
        else:
            a = 1
            for i in xrange(number - 1):
                b = 2 * a
                a = b
            return a