假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
注意:给定 n 是一个正整数
思路:
可以用动态规划来求解该题
跳到第n个台阶,只有两种可能
从第n-1个台阶跳1个台阶
从第n-2个台阶跳2个台阶
只需求出跳到第n-1个台阶和第n-2个台阶的可能跳法即可
F(n):n个台阶的跳法
递推公式:F(n)=F(n-1)+F(n-2)
不难发现这是一个斐波那契数列
代码:
# -*- coding:utf-8 -*-
class Solution:
def jumpFloor(self, number):
# write code here
if number <= 2:
return number
second=2
first=1
result=1
for i in range(3,number+1):
result=first+second
first=second
second=result
return result