- 技术博客
- 【数据结构与算法python】斐波那契数列的多种解决方案（递归、改进后的递归、动态规划）
1、引入（leecode试题）
2、解决方案
（1）传统解法
def climbStairs(n
):
f1
, f2
= 1, 2
while n
> 1:
f1
, f2
= f2
, f1
+ f2
n
-= 1
return f1
（2）递归解法
def climbStairs(n
):
if n
==1:
return 1
elif n
==2:
return 2
else:
return climbStairs
(n
-1)+climbStairs
(n
-2)
（3）带记忆性的递归解法
def climbStairs(n
,L
):
if n
==1:
L
[n
] =1
return 1
elif n
==2:
L
[n
] =2
return 2
elif L
[n
]>0:
return L
[n
]
else:
L
[n
] = climbStairs
(n
-1,L
)+climbStairs
(n
-2,L
)
return climbStairs
(n
-1,L
)+climbStairs
(n
-2,L
)
（4）动态规划解法
def climbStairs(n
,L
):
for i
in range(1,n
+1):
if i
==1:
L
[i
] = 1
elif i
==2:
L
[i
] = 2
else:
L
[i
] = L
[i
-1]+L
[i
-2]
return L
[n
]
