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 

這應該是比較簡單的方法了，受教了！