问题描述

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

思路

设f(n)表示青蛙跳上n阶的跳法，那么就有f(0)=1，f(1)=1，f(2)=2。如果青蛙要跳到第3阶，那么有两种方式：

• 从第2阶跳1级上第3阶
• 从第1阶跳2级上第3阶

于是有f(3)=f(2)+f(1)，以此类推，青蛙跳到第n阶有两种方式：

• 从第n-1阶跳1级上第n阶
• 从第n-2阶跳2级上第n阶

所以，我们可以得出：f(n)=f(n-2)+f(n-1)。于是这个问题的本质就类似于求斐波那契数列。

Python实现

class Solution(object):
    def __init__(self):
        self.f_list = [1,1]
    def numWays(self, n):
        if len(self.f_list)<n+1:
            self.get_f_list(n)
        return self.f_list[n]
    def get_f_list(self,n):
        for i in range(n+1-len(self.f_list)):
            self.f_list.append(self.f_list[-1]+self.f_list[-2])