1.题目描述

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?

爬楼梯，每次只能跨过一个或两个台阶，有多少种爬台阶的方式

2.题目分析

与斐波那契数列算法类似，递归调用 F(n)=F(n-1)+F(n-2)

3.解题思路

算法一：

1 class Solution(object): 2     def climbStairs(self, n): 3         """ 4         :type n: int 5         :rtype: int 6         """ 7         def steps(n): 8             if n==1: 9                 return 110             elif n==2:11                 return 212             else:13                 return steps(n-1)+steps(n-2)14         return steps(n)

算法二：

1 class Solution(object): 2     def climbStairs(self, n): 3         """ 4         :type n: int 5         :rtype: int 6         """ 7         if n==0: 8             return 0 9         elif n==1:10             return 111         elif n==2:12             return 213         else:14             x1,x2=1,215             while n-2>0:16                 x1,x2=x2,x1+x217                 n-=118             return f2

第一种算法采用的是递归调用函数本身，结果输入35的时候就Time Limit Exceeded，第二种算法没有递归调用函数，而是将值给了参数x1,x2

4.解题收获

在网上查了查递归与循环的区别，简单讲，递归效率低，但不易出错；循环速度快，但不易解决某些问题。（网址：https://www.cnblogs.com/BeyondAnyTime/archive/2012/05/19/2508807.html ）