题目描述
一个楼梯共有 n级台阶,每次可以走一级或者两级,问从第0级台阶走到第n级台阶一共有多少种方案。
python 代码
n = int(input())
#递归无剪枝
# def dfs(x): #第x台阶的方案
# if x == 1:return 1
# elif x == 2:return 2
# else:return dfs(x-1) + dfs(x-2)
# print(dfs(n))
#递归 + 记忆化剪枝
# st = [0 for _ in range(n+1)]
# def dfs(x):
# if x<=1:
# return 1
# if st[x]:
# return st[x]
# st[x] = dfs(x-2) + dfs(x-1)
# return st[x]
# dfs(n)
# print(st[n])
#记忆化 → python用户 Acwing不能用
# from functools import cache
# @cache
# def dfs(x):
# if x <= 1:
# return 1
# return dfs(x-1) + dfs(x-2)
# print(dfs(n))
#dp
# f = [1,2]
# if n == 1:
# print (1)
# else:
# for i in range(2,n):
# f.append(f[i-1] + f[i-2])
# print(f[-1])