专栏首页Petrichor的专栏leetcode: 70. Climbing Stairs

leetcode: 70. Climbing Stairs

Problem

# You are climbing a stair case. It takes n steps to reach to the top.
#
# Each time you can either climb 1 or 2 steps. 
# In how many distinct ways can you climb to the top?
#
# Note: Given n will be a positive integer.

AC

DP (动态规划):

class Solution():
    def climbStairs(self, n):
        pre, cur = 0, 1
        for _ in range(n):
            pre, cur = cur, pre + cur
        return cur

递归,会 Time Limit Exceeded (超时):

# Time Limit Exceeded
class Solution():
    def climbStairs(self, n):
        if n == 1:
            return 1
        if n == 2:
            return 2
        return self.climbStairs(n - 1) + self.climbStairs(n - 2)


if __name__ == "__main__":
    assert Solution().climbStairs(2) == 2

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • leetcode: 46. Permutations

    JNingWei
  • leetcode: 47. Permutations II

    JNingWei
  • leetcode: 80. Remove Duplicates from Sorted Array II

    leetcode: 26. Remove Duplicates from Sorted Array

    JNingWei
  • Quartz2D复习(四) --- 图层CALayer和动画CAAnimation

    1)、在ios中,能看得见摸得着的东西基本上都是UIView, 比如按钮、文本标签、文本输入框、图标等,这些都是UIView

    tandaxia
  • 百万在线的美拍直播弹幕系统的实时推送技术实践之路1、内容概述2、关于作者3、起步——快速上线4、问题——上线后暴露的问题及解决方法5、升级1——实现高可用保障6、升级2——使用长连接替换短连接轮询方案

    直播弹幕是直播系统的核心功能之一。如何迅速作出一个有很好扩展性的弹幕系统?如何应对业务迅速发展?相信很多工程师/架构师都有自己的想法。

    JackJiang
  • 支撑百万用户同时在线的高并发直播弹幕系统是如何炼成的?

    本文诠释了根据项目的发展阶段,直播弹幕系统进行平衡演进的过程。这三个阶段分别是快速上线,高可用保障体系建设,长连接演进。

    51CTO技术栈
  • 高通 display 驱动【转】

    233333
  • 微软和谷歌都曾遭遇过滑铁卢的智能家居,会在AI时代迎来复兴吗

    智能家居很可能可以称为IT历史上第一大坑,因为你掉下去后你可以在坑里发现比尔·盖茨、拉里·佩奇甚至雷军的相片。现在AI来了,它是会让这个大坑充满黄金还是会让这个...

    新智元
  • Kaggle | 全球听众最多的50首歌曲

    原文:https://maoli.blog.csdn.net/article/details/104478457

    润森
  • ReactiveCocoa 中 RACSignal 所有变换操作底层实现分析(上)

    在上篇文章中,详细分析了RACSignal是创建和订阅的详细过程。看到底层源码实现后,就能发现,ReactiveCocoa这个FRP的库,实现响应式(RP)是用...

    一缕殇流化隐半边冰霜

扫码关注云+社区

领取腾讯云代金券