Python两行实现斐波那契数列及动态规划改进

本文主要是介绍Python两行实现斐波那契数列及动态规划改进，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

递归

斐波那契数列本质可以看作一个递归，即：Fibonacci(n)=Fibonacci(n-1)+Fibonacci(n-2)

因此有：

#递归版Python代码
def Fibonacci(n):return n if n < 2 else Fibonacci(n-1)+Fibonacci(n-2)

递归代码简单明了，但时间和空间复杂度都较高，尤其是在n较大的情况下。可以考虑用动态规划做出改进。

动态规划

​对于Fibonacci数列，计算第100项的时候，需要计算第99项和98项；在计算第101项的时候，需要第100项和第99项，这时候你还需要重新计算第99项吗？不需要，你只需要在第一次计算的时候把它记下来就可以了。

​上述过程中需要再次计算的“第99项”，即为动态规划算法中的“重叠子问题”。如果没有计算过，就按照

这篇关于Python两行实现斐波那契数列及动态规划改进的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---