剑指09-变态跳台阶

Posted on | In |

题目描述

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

设n级的台阶的跳法数表示为F(n)

  • 按第一次跳的台阶数，可以将跳法空间分为互斥且互补的n个空间：
    • 第一次跳1个台阶，跳法有F(n-1)
    • 第一次跳2个台阶，跳法有F(n-2)
    • ...
    • 第一次跳n-1个台阶，跳法有F(1)
    • 第一次跳n个台阶，跳法有1
  • 因此F(n) = F(n-1)+F(n-2)+...+F(1)+1
  • 进而可得F(n)=2F(n-1)，其中F(1) = 1
1
2
3
4
5
6
7
8
9
class Solution:
    def jumpFloorII(self, number):
        # write code here
        if number == 0:
            return 1
        elif number == 1:
            return 1
        else:
            return 2*self.jumpFloorII(number-1)