dtcms 源码 android开发实战 Eclipse Opencv idea stream wso2 underscorejs vue图表 jquery的each循环 jquery查找子元素 jquery通过class获取元素 matlab中log函数 js原生点击事件 oracle增加主键 kubernetes安装 mysql入门 python基础练习 randomjava java数组删除 java取当前时间 行业软件下载 ip隐藏 右键菜单背景 flash基础 刷声望 selinux关闭 qq钱包实名认证 万能播放器电脑版 ps反向选择的快捷键 txplatform win98序列号 寂静城 内存条有什么用 mac办公软件 ppt背景音乐怎么关 聊呗电脑版 vue上传图片 刷机精灵下载 金鸡双刀
当前位置: 首页 > 学习教程  > python

【Leetcode】70. 爬楼梯(Climbing Stairs)

2021/2/8 10:44:10 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

No70. 爬楼梯 题目 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢? 注意:给定 n 是一个正整数。 示例1 输入: 2输出: 2解释: 有两种方法可以爬…

No70. 爬楼梯

题目

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?

注意:给定 n 是一个正整数。

示例1

  • 输入: 2
  • 输出: 2
  • 解释: 有两种方法可以爬到楼顶。
  1. 1 阶 + 1 阶
  2. 2 阶

示例2

  • 输入: 3
  • 输出: 3
  • 解释: 有三种方法可以爬到楼顶。
  1. 1 阶 + 1 阶 + 1 阶
  2. 1 阶 + 2 阶
  3. 2 阶 + 1 阶

思路:

第1阶有一种方法
第2阶可以从第0阶或第1阶上来,共两种方法
第3阶可以从第1阶或第2阶上来,共三种方法

原题目转化为求斐波那契数列,每次递归的时候先访问字典,如果不存在则进行求解并将其存入到字典中;如果存在则直接返回。

相当于做了剪枝操作。

解题代码(Python3)

class Solution:
    def climbStairs(self, n: int) -> int:
        def fibonacci(num):
            if num in dict:
                return dict[num]
            else:
                res = fibonacci(num-1) + fibonacci(num-2)
                dict[num] = res
                return res
        dict = {0:1,1:1}
        return fibonacci(n)

复杂度分析:

  • 时间复杂度 O(logn)
  • 空间复杂度 O(n) 需要用字典储存斐波那契数列

运行结果:

在这里插入图片描述


本文链接: http://www.dtmao.cc/news_show_2000300.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?