Leetcode_num13_Climbing Stairs

时间:2022-07-02 01:33:29

称号:

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?

非常easy的思路。由于一次能够走1~2步,所以到达第n级能够从第n-1级,也能够从第n-2级。

设到达第n级的方法有s(n)种,s(n)=s(n-1)+s(n-2)

一開始准备用递归做。代码例如以下:

class Solution:
# @param n, an integer
# @return an integer
def climbStairs(self, n):
if n<=2:
return n
else:
return self.climbStairs(n-1)+self.climbStairs(n-2)

结果在n=35的时候TLE了。这进一步说明递归的算法效率比較低,但从思路上比較简单明了。

于是,转向迭代了,代码例如以下:

class Solution:
# @param n, an integer
# @return an integer
def climbStairs(self, n):
if n<=1:
return n
else:
s=[0 for i in range(n)]
s[0]=1 #到达第1级
s[1]=2 #到达第2级
for i in range(2,n):
s[i]=s[i-1]+s[i-2]
return s[n-1] #到达第n级

在此引入一个数组s,记录到达第n级的方法,然实际要求的返回值是s[n],数组s中的前n-1项存储值是多余的。

于是进行改进。设s1为走一步到达方法数。s2为走两步到达的方法数。那么到达第n级台阶时,s(n)=s1+s2,当中s1=s(n-1),s2=s(n-2);到达第n+1级台阶时。s(n+1)=s1+s2,当中s1=s(n)=上一步的s1+s2, s2=s(n-1)=上一步的s1,所以仅仅须要记录s1和s2的值。无需记录n个值

class Solution:
# @param n, an integer
# @return an integer
def climbStairs(self, n):
if n<=1:
return n
else:
s1=1
s2=1
for i in range(1,n):
s=s1+s2
s2=s1
s1=s
return s

这应该是比較简单的方法了。受教了。

版权声明:本文博客原创文章。博客,未经同意,不得转载。

Leetcode_num13_Climbing Stairs的更多相关文章

  1. &lbrack;LeetCode&rsqb; Climbing Stairs 爬*问题

    You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb ...

  2. &lbrack;LintCode&rsqb; Climbing Stairs 爬*问题

    You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb ...

  3. Leetcode&colon; climbing stairs

    July 28, 2015 Problem statement: You are climbing a stair case. It takes n steps to reach to the top ...

  4. LintCode Climbing Stairs

    You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb ...

  5. 54&period; Search a 2D Matrix &amp&semi;&amp&semi; Climbing Stairs (Easy)

    Search a 2D Matrix Write an efficient algorithm that searches for a value in an m x n matrix. This m ...

  6. Climbing Stairs

    Climbing Stairs https://leetcode.com/problems/climbing-stairs/ You are climbing a stair case. It tak ...

  7. 3月3日&lpar;6&rpar; Climbing Stairs

    原题 Climbing Stairs 求斐波那契数列的第N项,开始想用通项公式求解,其实一个O(n)就搞定了. class Solution { public: int climbStairs(int ...

  8. Cllimbing Stairs &lbrack;LeetCode 70&rsqb;

    1- 问题描述 You are climbing a stair case. It takes n steps to reach to the top. Each time you can eithe ...

  9. leetCode 70&period;Climbing Stairs (爬楼梯) 解题思路和方法

    Climbing Stairs  You are climbing a stair case. It takes n steps to reach to the top. Each time you ...

随机推荐

  1. Myeclipse Templates详解&lpar;一&rpar; —— Java模板基础

    目录 Templates简介 MyEclipse自带Templates详解 新建Template 自定义Template 因为自己比较懒,尤其是对敲重复代码比较厌恶,所以经常喜欢用快捷键和模板,Mye ...

  2. 基于Autofac&comma; Castle&period;DynamicProxy的动态WCF解决方案&lpar;原创&rpar;

    本方案解决了下面3个主要的问题: 1.减少配置,为了避免每次新增service都需要去修改配置文件,包括服务器端跟各个客户端的. 2.能够使用函数重载,泛型函数,以及泛型类. 3.使项目能够快速地在w ...

  3. &lbrack;原&rsqb;AppPoolService-IIS应用程序池辅助类(C&num;控制应用程序池操作)

    using System.Collections.Generic; using System.DirectoryServices; using System.Linq; using Microsoft ...

  4. Java容器类接口的选择

    我们知道Java容器类实际提供了四类接口:Map,List,Set和Queue,如下图所示,每种接口都有不止一个版本的实现,如果在实际编写程序时需要使用某种接口时该如何选择. 从Oracle的Java ...

  5. iOS开发的22个奇谲巧技

    结合自身的实践开发经验总结出了22个iOS开发的小技巧,以非常欢乐的语调轻松解决开发过程中所遇到的各种苦逼难题,光读着便已忍俊不禁. 1. TableView不显示没内容的Cell怎么办? 类似于图1 ...

  6. Prime Path(poj 3126&rpar;

    Description The ministers of the cabinet were quite upset by the message from the Chief of Security ...

  7. JQ 更改li 颜色

    <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/ ...

  8. 提交服务器 post get

    HttpRequest Post or Get // method --- WebRequestMethods.Http.Post 或 WebRequestMethods.Http.Get priva ...

  9. eclipse 打包 jar 到 Linux上运行

    1.选择需要打包的项目,右键 Export 2.选择Runnable JAR file,然后点击 Next 3.选择jar包运行的main类,以及定义jar包的名字,保存的地方 4.将 导出来的 ja ...

  10. 【转】MySQL中的共享锁与排他锁

    在MySQL中的行级锁,表级锁,页级锁中介绍过,行级锁是Mysql中锁定粒度最细的一种锁,行级锁能大大减少数据库操作的冲突.行级锁分为共享锁和排他锁两种,本文将详细介绍共享锁及排他锁的概念.使用方式及 ...