题解 | #跳台阶#

跳台阶

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阶跳两步。
故:

可依上式编写递归。

但程序超过时限,尝试稍作优化,即利用

重复利用 的值,并减少递归次数。

测试通过,但还是很慢😥
全部评论

相关推荐

ResourceUtilization:四六级不愧是大学最有用的证之一
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务