题解 | #跳台阶#
跳台阶
http://www.nowcoder.com/practice/8c82a5b80378478f9484d87d1c5f12a4
# -*- coding:utf-8 -*- class Solution: def jumpFloor(self, number): # write code here # base case if number <= 3: return number # n = either n-2 +2 or n-1+1 iCondition1 = self.jumpFloor(number-1) # starting from 1 by +1 and afterward iCondition2 = iCondition1 - self.jumpFloor(number-3) # starting from 2 by +2 return iCondition1 + iCondition2
Tag 里写了考察知识点是递归,故尝试仅用递归解题。
站在第n阶的角度考虑,有两种方式从上一个状态达到该状态,即:
1. 从第n-1阶跳一步。
2. 从第n-2阶跳两步。
故:
可依上式编写递归。
但程序超过时限,尝试稍作优化,即利用
重复利用
的值,并减少递归次数。
测试通过,但还是很慢😥