1 - Easy - 爬楼梯

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

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

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

示例 1：

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。

1. 1 步 + 1 步
2. 2 步
   示例 2：

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。

1. 1 步 + 1 步 + 1 步
2. 1 步 + 2 步
3. 2 步 + 1 步

实际上是斐波那契数列

class Solution(object):
    def climbStairs(self, n):
        steps = [1, 2]
        for i in range(3, n+1):
            steps.append(steps[-1] + steps[-2])
        return steps[n-1]

下面的方法可以计算出所有的走法，但是超时

class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        steps = [["1"], 
                 ["11", "2"]]
        if n < 3:
            return len(steps[n-1])
        for i in range(3, n+1):
            last = steps[-1]
            temp = []
            for s in last:
                _left = "1" + s
                if _left not in temp:
                    temp.append(_left)
                _right = s + "1"
                if _right not in temp:
                    temp.append(_right)
            lastlast = steps[-2]
            for s in lastlast:
                _left = "2" + s
                if _left not in temp:
                    temp.append(_left)
                _right = s + "2"
                if _right not in temp:
                    temp.append(_right)
            steps.append(temp)
        return len(steps[n-1])