Python每日一练--------递归，动态规划（爬楼梯）
（第三天）
题目：
考官：假设你正在爬楼梯。需要n阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
考员：我怎么做，我做电梯，现在谁还爬楼梯。
考官：（￥%%#）那太可惜了，我们公司没有电梯。
。。。。。。
示例 1：输入：n = 2输出：2解释：有两种方法可以爬到楼顶。1. 1 阶 + 1 阶2. 2 阶
示例 2：
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
分析题目：W（n）表示有n种方法当只有没有台阶或者是只有一阶台阶，只有一种方法 。
当有两阶台阶
当有三阶台阶
当有n阶台阶
也可以用逆推的方法，当你站在第n阶，你的后一步只能是在n-1阶上来，或者是从n-2阶上来，则
W（n）= W（n-1）+W（n-2），类似数学的归纳法。现在来找递归的边界，试子中W（n-2）
n-2>=0 ,所以 n>=2.
代码实现
def method(n):# 传入参数 if n == 0 or n == 1: # 当只有0阶或一阶台阶时返回1 return 1 else: # 当n>=2时调用method函数，来构造公式W(n)=W(n-1)+W(n-2) return method(n-1) + method(n-2)if __name__ == '__main__': while True:# 循环语句可不断输入n的值 n = int(input('enter n:')) # input获取的n为字符串需要用int（）转换成数值 way = method(n) print(way)结果如下
但是这种递归算法耗时比较长因为有计算重复的步骤
占用的栈也多，当n的值足够大时栈可能会溢出，改进，使用记忆递归
# 多了一层函数1def solution(n): def method(i, rema): # rema其实是一个只包含0的列表，因为给rema传入的实参为[0]*(n+1) if i == 0 or i == 1: return 1 if rema[i] == 0: # rema的第i个元素为零说明没有计算过 rema[i] = method(i - 1, rema) + method(i - 2, rema) # 继续调用method函数，递归 return rema[i] return method(n, [0] * (n + 1)) #调用method函数传入实参，solution最终的返回结果为rema[i]if __name__ == '__main__': while True: n = int(input('enter n:')) way = method(n) print(way)在继续优化
def method(n): # 不用两层函数 rema = [0] * (n + 1) # rema是一个有n+1个零的列表 rema[0] = rema[1] = 1 # 相当于只有0和1阶楼梯的情况 for i in range(2, n + 1): # 0和1阶的情况已给出，i从2开始，因为有n阶所以range（2，n+1） rema[i] = rema[i - 1] + rema[i - 2] return rema[-1] # 返回rema列表最后一个数if __name__ == '__main__': while True: n = int(input('enter n:')) way = method(n) print(way)出现一个疑问rema[-1]相当于返回rema[i]但是为什么不用rema[i]，因为i是局部变量，for循环提供i，但是return rema[i]在for外，使用则会引发local variable 'i' referenced before assignment错误（局部变量引用在分配前）。
到这还能再优化吗？当然考员可是要做电梯的
def method(n): # 由公式W(n)=W(n-i)+W(n-2),只需要W(n-i)，W(n-2)，将rema列表换成变量 a = b = 1 for i in range(2, n + 1): a, b = b, a + b return bif __name__ == '__main__': while True: n = int(input('enter n:')) way = method(n) print(way)考官：我马上给公司装个电梯。
链接：https://leetcode-cn.com/problems/climbing-stairs/solution/zhi-xin-hua-shi-pa-lou-ti-zhi-cong-bao-l-lo1t/来源参考：力扣（LeetCode）
