爬楼梯问题
题目:小明同学爬n阶楼梯,他一次可以上一阶,也可上两阶。问小明上楼的方式有多少种?
解: 假设楼梯有一个台阶,则只有一种方法。 假设楼梯有两个台阶,则有两种(一次走一阶,走两次。或者一次走两阶,走一次。)。 假设楼梯有三阶呢? 你先想一下:从哪里都可以直接走到三阶? 显然是在第一个台阶处,一下子走两阶直到三阶。或者是在第二阶,一下子走一阶,就到三阶了。。 。。 以此类推: n阶的时候有多少种方法? 那显然就是F(n-1) 加上F(n-2)。 注: F(n)表示走到n阶有多少种方法。
由此,我们用动态规划的思想, 可以写出下面的式子:
代码实现(分别采用了递归和迭代)
def dp_solver(n):
# 迭代解法
temp = [0] * n # 建立一个长度为n的列表
if n == 1:
temp[0] = 1
return temp
elif n == 2:
temp[0] = 1
temp[1] = 2
return temp
else:
temp[0] = 1
temp[1] = 2
for i in range(2, n):
temp[i] = temp[i-1] + temp[i-2] # 这里主要考虑到列表是从编号为0出开始存值
return temp
def recursion(n):
# 递归解法
if n == 1:
return 1
if n == 2:
return 2
return recursion(n-1) + recursion(n-2)
if __name__ == '__main__':
# 假设当前台阶我们设置为50层,问有多少种方法
n = 10
solve = dp_solver(n)
print("爬各个层的方法:", solve) # 打印爬各个层的方法
print("当台阶数为:{}, 总共有{}种爬法!!!".format(n, solve[n-1]))
solve2 = recursion(n)
print("当台阶数为:{}, 总共有{}种爬法!!!".format(n, solve2))
结果输出: