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?

Note: Given n will be a positive integer.

Example 1:

Input: 2
Output:  2
Explanation:  There are two ways to climb to the top.

1. 1 step + 1 step
2. 2 steps

Example 2:

Input: 3
Output:  3
Explanation:  There are three ways to climb to the top.

1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

动态规划，数列 1 2 3 5 8 13 21

class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        res = [1, 2]
        i = 3
        while i <= n:
            res.append(res[i-3]+res[i-2])
            i += 1
        return res[n-1]

动态规划模拟所有步数，时间超限

res = {1: ["1"], 2: ["11", "2"]}
    i = 3
    while i <= n:
        res[i] = []
        for r in res[i - 1]:
            for j in range(len(r)):
                temp_s = r[:j] + "1" + r[j:]
                if temp_s not in res[i]:
                    res[i].append(temp_s)
        for r in res[i - 2]:
            for j in range(len(r)):
                temp_s = r[:j] + "2" + r[j:]
                if temp_s not in res[i]:
                    res[i].append(temp_s)
        print(i,":",res[i])
        i += 1
    return res