首页 > 代码库 > Leetcode_num13_Climbing Stairs

Leetcode_num13_Climbing Stairs

题目:

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?

很简单的思路,因为一次可以走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