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) 

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