70 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?

Example 1:

Case 1:
    Input: 2
    Output: 2
Case 2:
    Input: 3
    Output: 3

Note:

1. Given n will be a positive integer.

题目翻译

有n层楼梯，每次只能爬0或1阶台阶。总有有多少种方式可以爬到楼梯顶部？

示例1：

示例1：
    输入： 2
    输出： 2
示例2：
    输入： 3
    输出： 3

注意：

1. 输入台阶数 n 为正整数

解题方案

标签： Dynamic Programming

思路：

• 问题符合斐波那契数列的描述： 设总共有 n 阶台阶，可能的方案有$s(n)$种。考虑最后一步决策：如何到达第 n 层，有两种方案：

  1. 最后一步上1个台阶，那么剩下的 $n-1$ 阶台阶的方案为：$s_1=s(n-1)$
  2. 最后一步上2个台阶：那么剩下的 $n-2$ 阶台阶的方案为：$s_2=s(n-2)$

  3. 那么总的方案数目：$s(n)=s_1+s_2=s(n-1)+s(n-2)$

     正好是斐波那契数列的样子

代码：

class Solution:
    def climbStairs(self, n):
        """ 
        :type n: int 
        :rtype: int 
        """ 
        dp = [1  for i in range(n+1)] 
        for i in range(2, n+1): 
            dp[i] = dp[i-1] + dp[i-2] 
        return dp[n]

参考资料

• http://blog.csdn.net/u013632190/article/details/52050409
• 作者：一路洒满阳光XD