题解 | #跳台阶#
跳台阶
http://www.nowcoder.com/practice/8c82a5b80378478f9484d87d1c5f12a4
这个其实和斐波那契数列一样，就是
假设f[i]表示在第i个台阶上可能的方法数。逆向思维。如果我从第n个台阶进行下台阶((跳到n-1的方法数为f(n)))，下一步有2中可能，一种走到第n-1个台阶(跳到n-1的方法数为f(n-1))，一种是走到第n-2个台阶(跳到n-1的方法数为f(n-2))，而这两种方式下面又对应n-2，n-3和n-3,n-4个台阶，以此一直递归迭代到最前面。所以f[n] = f[n-1] + f[n-2].，
然后我又犯了递归的老毛病，导致run的时候超出运算时间
# -*- coding:utf-8-*-
classSolution:
def jumpFloor(self, number):
# write code here
ifnumber == 1:
return1
elif number == 2:
return2
else:
returnself.jumpFloor(number-1) + self.jumpFloor(number-2)
# -*- coding:utf-8-*-
classSolution:
def jumpFloor(self, number):
# write code here
ifnumber == 1:
return1
elif number == 2:
return2
else:
Fone = 1
Ftwo = 2
fori in range(3, number+1):
Fn = Fone + Ftwo
Fone = Ftwo
Ftwo = Fn
returnFn
投递深圳虾皮信息科技有限公司等公司10个岗位
查看15道真题和解析