本文共 1441 字，大约阅读时间需要 4 分钟。

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

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

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

示例 1：

输入： 2

输出： 2

解释： 有两种方法可以爬到楼顶。

1.  1 阶 + 1 阶

2.  2 阶

输入： 3

输出： 3

解释： 有三种方法可以爬到楼顶。

1.  1 阶 + 1 阶 + 1 阶

2.  1 阶 + 2 阶

3.  2 阶 + 1 阶

假如有n个阶梯，可以分成两部分来走，先走一个阶梯，再走剩下的n-1个阶梯，或者先走两个阶梯，再走剩下的n-2个阶梯，有两种组合方式。对于剩下的n-1或者n-2个阶梯怎么走呢？也是相同的处理方法，先走一个阶梯或者先走两个阶梯，还是两种组合。一直递归下去即可。

显然，阶数为n时，我们的组合有f(n-1) + f(n-2)种，其中f(n)表示n个阶梯对应的走法。

状态转移方程：f(n) = f(n-1) + f(n-2)

class Solution:    def climbStairs(self, n):        if n == 1:            return 1        if n == 2:            return 2        else:            return self.climbStairs(n-1) + self.climbStairs(n-2)

但是这个做法的时间超过了

另一种递推的方法：

class Solution:    def climbStairs(self, n):        """        :type n: int        :rtype: int        """        num = [0, 1, 2] # 这里的元素设置是为了方便下标一一对应        if n == 1:            return num[1]        if n == 2:            return num[2]        else:            for i in range(3, n+1): # 这里range是到n为止                num.append(num[i-1]+num[i-2])            return num[n]

以下是Java版本：

题解：

这道题就是经典的讲解最简单的DP问题的问题。。

假设梯子有n层，那么如何爬到第n层呢，因为每次只能怕1或2步，那么爬到第n层的方法要么是从第n-1层一步上来的，要不就是从n-2层2步上来的，所以递推公式非常容易的就得出了：

dp[n] = dp[n-1] + dp[n-2]

如果梯子有1层或者2层，dp[1] = 1, dp[2] = 2，如果梯子有0层，自然dp[0] = 0 

public class ClimbingStairs {	public int climbStairs(int n) {	       if(n==0||n==1||n==2)	          return n;	       int [] dp = new int[n+1];	       dp[0]=0;	       dp[1]=1;	       dp[2]=2;	         	       for(int i = 3; i

转载地址：http://fsuvi.baihongyu.com/