首页 > 其他分享 >70. 爬楼梯

70. 爬楼梯

时间:2023-11-13 21:03:00浏览次数:29  
标签:楼顶 爬楼梯 int self climbStairs 70 return

目录

题目

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

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

示例 1:

输入:n = 2
输出:2
解释:有两种方法可以爬到楼顶。1. (1 阶 + 1 阶);2. (2 阶)

示例 2:

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

法一、暴力

  • 思路:站到最后一梯往回看,可知:可以从n-1阶跨上来,也可以从n-2阶跨上来,其实每一阶都是如此

  • 相当于斐波那契数列

class Solution:
    def climbStairs(self, n: int) -> int:
        if n==0 or n==1:
            return 1
        return self.climbStairs(n-1)+self.climbStairs(n-2)
  • 超时

法二、动态规划

class Solution:
    def climbStairs(self, n: int) -> int:
        f=[0]*(n+1)
        f[0]=f[1]=1
        for i in range (2,n+1):
            f[i]=f[i-1]+f[i-2]
        return f[n]

标签:楼顶,爬楼梯,int,self,climbStairs,70,return
From: https://www.cnblogs.com/lushuang55/p/17830140.html

相关文章

  • 服务器Windows Server发布.NET Core项目出现HTTP错误500.19 - Internal Server Error[
    服务器WindowsServer发布.NETCore项目出现HTTP错误500.19-InternalServerError[错误代码:0x8007000d]经检查,发现是因为缺少【ASPNETCoreModuleV2】解决方案:到微软官方下载相应.net版本的HostingBundle  https://dotnet.microsoft.com/en-us/download/dotnet  下......
  • 算法题:跳房子问题(爬楼梯问题进阶) 求解受限制情况下的方案数目
    问题跳房子,规定总共有n个格子,每次可以选择跳1个格子、2个格子或3个格子,但是下一步不能和当前选择的跳跃距离一样,计算总共有多少种跳房子方案。分析这就是经典爬楼梯问题的进阶,仅仅换了个说法,但是比经典的爬楼梯问题难了不少,传统的爬楼梯问题一次可以上1或2个台阶没有连续动作......
  • windwos小工具推荐,只有700kb不到,但作用确很大!
    看个图,简单了解下,获取地址在文末RAMMap:Windows的物理内存使用分析工具RAMMap是一款由MicrosoftSysinternals团队开发的免费工具,它可以让你以不同的方式查看Windows系统的物理内存使用情况。它支持WindowsVista及更高版本的客户端和服务器操作系统。RAMMap有几个不......
  • 「语音转换新速度」— 探秘Whisper JAX的70倍速提升
    在AI的众多分支中,语音识别技术的突破性进展尤为引人瞩目。由SanchitGandhi开发的WhisperJAX就是这一创新旅程中的新星。它是OpenAI的Whisper模型的JAX版本,实现了在TPU上高达70倍的速度提升,这不仅是对现有技术的重大突破,更是对未来潜力的一次展现。技术优势WhisperJAX继承了原始W......
  • 波士顿大学「鸭嘴兽-70B」登顶Hugging Face大模型排行榜!高效数据集+独特LoRA微调是关
    HuggingFace上的开源大模型排名榜又更新了,这次荣登榜一的是:鸭嘴兽(Platypus2-70B)!和现在抱脸开源榜单上大部分的模型一样,鸭嘴兽是来自波士顿大学的研究人员基于Llama2微调而来。同时,鸭嘴兽的进步就像之前所有的开源大模型那样:在提升性能的同时,使用更少的计算资源和数据。一个13B的......
  • 算法day1数组|力扣704二分查找,27移除元素
    数组基础理论数组是存放在连续内存空间上的相同类型数据的集合。可以通过下标轻松获取数据,但是增删元素的时候需要移动其他元素Vector和array的区别vector的底层实现是array,但是vector是容器不是数组数组的元素不能删除,只能覆盖小技巧:取中间intmid=l+r>>1;//有时候怕溢......
  • [题解]CFgym103470E Paimon Segment Tree
    PaimonSegmentTree区间加,求一段时间内的区间平方和。\(n,m,q\le5\times10^4\)。对时间维差分一下,变成询问区间历史平方和。离线下来扫描线,扫描线维护时间维,数据结构维护序列维。考虑维护二元组\((a,s)\)表示当前位置值为\(a\),历史平方和为\(s\)。可以发现怎......
  • [每周一更]-(第70期):常用的GIT操作命令
    1、增删文件#添加当前目录的所有文件到暂存区$gitadd.#添加指定文件到暂存区$gitadd<file1><file2>...#添加指定目录到暂存区,包括其子目录$gitadd<dir>#删除工作区文件,并且将这次删除放入暂存区$gitrm[file1][file2]...#停止追踪指定文件,但该......
  • 表碎片整理时shrink和move如何选择 --高水位回收 转:http://blog.itpub.net/29821
    整理表碎片通常的方法是move表,当然move是不能在线进行的,而且move后相应的索引也会失效,oracle针对上述不足,在10g时加入了shrink,那这个方法能不能在生产中使用呢?     shrink的一个优点是能在线进行,不影响表上的DML操作,当然,并发的DML操作在shrink结束的时刻会出现短暂的block;s......
  • 集成电路(IC)MAX98050ENX、MAX22707AUB、MAX17543ATP、MAX40008ANT高效、低功耗器件产品
    1、MAX98050ENX音频编解码器是一款高性能、低功耗器件,集成了低延迟数字滤波器,用于无线耳戴式设备、头戴式设备和耳机。MAX98050具有一个单声道播放通道,带有一个5频段双四路均衡器和一个高效、全差分混合AB/D类耳机放大器。播放耳机放大器经过优化,可以实现最低输出噪声和静态功耗,同......