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
