题干：

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数

DFS算法

class Solution(object):def climbStairs(self, n):""":type n: int:rtype: intDFS"""re=[0]def DFS(curr_stairs):if curr_stairs==0:re[0]+=1elif curr_stairs<0:passelse:DFS(curr_stairs-1)DFS(curr_stairs-2)DFS(n)return re[0]
a=Solution()
print a.climbStairs(10)

动态规划（DP）算法

递归写法：

class Solution(object):def climbStairs(self, n):""":type n: int:rtype: intDFS"""def DP(curr_stairs):if curr_stairs==1:return 1elif curr_stairs==0:return 1else:return DP(curr_stairs-1)+DP(curr_stairs-2)return DP(n)

到了38就超时！本质上还是一样的开销啊！递归写法不行开销太大

class Solution(object):def climbStairs(self, n):""":type n: int:rtype: intDFS"""def DP(n):i=1#DP(0)=1j=1#DP(1)=1k=#DP(1)=1,为了防止n=1不进入循环，导致k没有值for m in range(n-1):#滚动数组k=i+ji=jj=kreturn kreturn DP(n)

滚动数组写法