Leetcode-Easy 70. Climbing Stairs

21. Merge Two Sorted Lists

  • 描述: 有n阶楼梯,每步只能走1个或2个台阶,请问到达第n阶楼梯一共有多少走法?
  • 思路: 动态规划 程序从 i=3 开始迭代,一直到 i=n 结束。每一次迭代,都会计算出多一级台阶的走法数量。迭代过程中只需保留两个临时变量a和b,分别代表了上一次和上上次迭代的结果。 为了便于理解,我引入了temp变量。temp代表了当前迭代的结果值。
  • 代码
 class Solution:
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        
        # 递归 time limit
#         if n==1 or n==2:
#             return n
        
#         return Solution.climbStairs(self,n-1)+Solution.climbStairs(self,n-2)
        
        ## 备忘录算法 time limit
#         data={}
#         if n==1 or n==2:
#             return n
        
#         if n in data:
#             return data['n']
#         else:
#             value=Solution.climbStairs(self,n-1)+Solution.climbStairs(self,n-2)
#             data['n']=value
#             return value
        ## 动态规划
        if n==1 or n==2:
            return n
        first=1
        second=2
        temp=0
        for i in range(n-2):
            temp=first+second
            first=second
            second=temp
        return temp

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏编程理解

数据结构(十二):最短路径(Dijkstra算法)

Dijkstra 算法使用贪心策略计算从起点到指定顶点的最短路径,通过不断选择距离起点最近的顶点,来逐渐扩大最短路径权值,直到覆盖图中所有顶点。

33120
来自专栏数据结构与算法

二分图相关定理

定义:若选择一个点说明选择与它相连的所有边,最小顶点覆盖就是选择最少的点来覆盖所有的边。

12430
来自专栏恰童鞋骚年

数据结构基础温故-5.图(中):最小生成树算法

图的“多对多”特性使得图在结构设计和算法实现上较为困难,这时就需要根据具体应用将图转换为不同的树来简化问题的求解。

16820
来自专栏趣学算法

数据结构 第17讲 沟通无限校园网——最小生成树(kruskal算法)

构造最小生成树还有一种算法,Kruskal算法:设G=(V,E)是无向连通带权图,V={1,2,…,n};设最小生成树T=(V,TE),该树的初始状态为只有n...

18520
来自专栏算法修养

FZU 2087 统计树边

Problem 2087 统计树边 Accept: 197 Submit: 571 Time Limit: 1000 mSec Memory...

356110
来自专栏数据结构与算法

洛谷P3209 [HNOI2010]PLANAR(2-SAT)

题目描述 若能将无向图G=(V,E)画在平面上使得任意两条无重合顶点的边不相交,则称G是平面图。判定一个图是否为平面图的问题是图论中的一个重要问题。现在假设你要...

34860
来自专栏移动开发面面观

OpenGL ES——导入.stl格式的3D模型

22340
来自专栏生信小驿站

Python数据处理从零开始----第四章(可视化)(7)(多图合并)目录正文

=========================================================

9210
来自专栏郭耀华‘s Blog

知乎问题代码

12020
来自专栏转载gongluck的CSDN博客

H.264格式分析

一.H.264基本流结构 H.264 的基本流(elementary stream,ES)的结构分为两层,包括视频编码层(VCL)和网络适配层(NAL)。视频编...

81350

扫码关注云+社区

领取腾讯云代金券