称号:
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的更多相关文章
-
[LeetCode] Climbing Stairs 爬*问题
You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb ...
-
[LintCode] Climbing Stairs 爬*问题
You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb ...
-
Leetcode: climbing stairs
July 28, 2015 Problem statement: You are climbing a stair case. It takes n steps to reach to the top ...
-
LintCode Climbing Stairs
You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb ...
-
54. Search a 2D Matrix &;&; Climbing Stairs (Easy)
Search a 2D Matrix Write an efficient algorithm that searches for a value in an m x n matrix. This m ...
-
Climbing Stairs
Climbing Stairs https://leetcode.com/problems/climbing-stairs/ You are climbing a stair case. It tak ...
-
3月3日(6) Climbing Stairs
原题 Climbing Stairs 求斐波那契数列的第N项,开始想用通项公式求解,其实一个O(n)就搞定了. class Solution { public: int climbStairs(int ...
-
Cllimbing Stairs [LeetCode 70]
1- 问题描述 You are climbing a stair case. It takes n steps to reach to the top. Each time you can eithe ...
-
leetCode 70.Climbing Stairs (爬楼梯) 解题思路和方法
Climbing Stairs You are climbing a stair case. It takes n steps to reach to the top. Each time you ...
随机推荐
-
Myeclipse Templates详解(一) —— Java模板基础
目录 Templates简介 MyEclipse自带Templates详解 新建Template 自定义Template 因为自己比较懒,尤其是对敲重复代码比较厌恶,所以经常喜欢用快捷键和模板,Mye ...
-
基于Autofac, Castle.DynamicProxy的动态WCF解决方案(原创)
本方案解决了下面3个主要的问题: 1.减少配置,为了避免每次新增service都需要去修改配置文件,包括服务器端跟各个客户端的. 2.能够使用函数重载,泛型函数,以及泛型类. 3.使项目能够快速地在w ...
-
[原]AppPoolService-IIS应用程序池辅助类(C#控制应用程序池操作)
using System.Collections.Generic; using System.DirectoryServices; using System.Linq; using Microsoft ...
-
Java容器类接口的选择
我们知道Java容器类实际提供了四类接口:Map,List,Set和Queue,如下图所示,每种接口都有不止一个版本的实现,如果在实际编写程序时需要使用某种接口时该如何选择. 从Oracle的Java ...
-
iOS开发的22个奇谲巧技
结合自身的实践开发经验总结出了22个iOS开发的小技巧,以非常欢乐的语调轻松解决开发过程中所遇到的各种苦逼难题,光读着便已忍俊不禁. 1. TableView不显示没内容的Cell怎么办? 类似于图1 ...
-
Prime Path(poj 3126)
Description The ministers of the cabinet were quite upset by the message from the Chief of Security ...
-
JQ 更改li 颜色
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/ ...
-
提交服务器 post get
HttpRequest Post or Get // method --- WebRequestMethods.Http.Post 或 WebRequestMethods.Http.Get priva ...
-
eclipse 打包 jar 到 Linux上运行
1.选择需要打包的项目,右键 Export 2.选择Runnable JAR file,然后点击 Next 3.选择jar包运行的main类,以及定义jar包的名字,保存的地方 4.将 导出来的 ja ...
-
【转】MySQL中的共享锁与排他锁
在MySQL中的行级锁,表级锁,页级锁中介绍过,行级锁是Mysql中锁定粒度最细的一种锁,行级锁能大大减少数据库操作的冲突.行级锁分为共享锁和排他锁两种,本文将详细介绍共享锁及排他锁的概念.使用方式及 ...