python动态规划之Fibobacci数列

本文主要是介绍python动态规划之Fibobacci数列，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

1简单的递归:当前值f(n)=f(n-1)+f(n-2)

Class Solution():
	def Fibonacci(self,n):
		if(n<=2):
			return n
		return self.Fibonacci(n-1) + self.Fibonacci(n-2)

每一层会发生两次递归。很多计算是重复的，效率低下，n值大就会导致超时

2尾递归：尾部调用递归函数，且每一层只产生一次递归
从n计数到1，n每次减1，f(n-2) = f(n-1) + f(n) = b + a

class Solution:
    def climbStairs(self, n: int) -> int:
        if (n<=2):
            return n
        return self.Fibonacci(n,a=1,b=1)
    def Fibonacci(self,n,a,b):
        if n == 1:
            return b #最后一层，返回b，b为当前层的值
        return self.Fibonacci(n-1,a=b,b=a+b) #f(n-2) = f(n-1) + f(n) 

非递归
非递归实现很简单，效率更高

这篇关于python动态规划之Fibobacci数列的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！