Python教程

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数列的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!