Leetcode-Easy 70. Climbing Stairs

致Great

发布于 2018-04-11 16:41:15

6270

发布于 2018-04-11 16:41:15

文章被收录于专栏：程序生活

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

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2018.03.20 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法