70 Climbing Stairs

原题链接：Climbing Stairs

本题是斐波那契数列，先上代码：

class Solution:
    # @param {integer} n
    # @return {integer}
    def climbStairs(self, n):
        if n == 1:
            return 1
        if n == 2:
            return 2
        a, b = 1, 1
        while n:
            a, b = b, a + b
            n -= 1
        return a

分析问题：
我先在纸上写下前几步的结果，观察规律。当n=1时，方法数为1；当n=2时，方法数为2；当n=3时，（由于我们只能选择上1层或者2层）我们先选择开始走1层这个方案，剩下两层，那么方法数就是n=2的方法数，然后再选择开始走2层这个方案，剩下一层，那么方法数就是n=1的方法数，因此n=3时的总方法数就是n=1时的方法数加上n=2时的方法数；
n=4时，先走1层的话，剩下3层，方法数为n=3，先走2层的话，剩下2层，方法数为n=2，因此n=4时的总方法数为n=2时的方法数加上n=3时的方法数。
由此，可发现规律，即是斐波那契数列。