70. Climbing Stairs.py

'''这个题其实是一个斐波那契数列，第n个台阶可以由第n-1个台阶一次走一步，也可以第n-2个台阶一次走两步，所以F[n]=F[n-1]+F[n-2]'''
def climbStairs(n):
	a = b = 1
	for _ in range(n):
	    a, b = b, a + b
	return a
result = climbStairs(11)
print(result)
'''注意：a, b = b, a + b和这个用法：
a = b, b = a + b不一样'''
'''
我最开始卡这种情况上了：当一共有6个台阶的时候:1+5+6+1=13
分以下4种情况讨论：
全是1：1:111111
1个2：5:21111,12111,11211,11121,11112
2个2：6:2121,1212,2112,(2211,1221,1122)这个括号里的组合是我一开始没想到的
3个2：1:222
'''