青蛙跳台阶python

题目描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后顺序算不同的结果）。

示例1

输入

2

输出

2

示例2

输入

3

输出

3

解法1：递归（会超时）

class Solution:
def jumpFloor(self, number):
if number==1:
return 1
if number==2:
return 2
return self.jumpFloor(number-1)+self.jumpFloor(number-2)

解法2：循环

class Solution:
def jumpFloor(self, number):
if number==1:
return 1
if number==2:
return 2
a=1
b=2
for i in range(3,number+1):
c=a+b
a=b
b=c
return c

解法3：动态规划

class Solution:
def jumpFloor(self, number):
if number==1:
return 1
if number==2:
return 2
dp=[0]*(number+1)
dp[1]=1
dp[2]=2
for i in range(3,number+1):
dp[i]=dp[i-1]+dp[i-2]
return dp[number]