斐波那契数列

斐波那契数列_牛客题霸_牛客网

问题简述

略

思路

• dp(i) := dp(i-1) + dp(i-1)

Python

class Solution:
    def Fibonacci(self , n: int) -> int:
        
        from functools import lru_cache
        
        @lru_cache(maxsize=None)
        def dp(i):
            if i in (1, 2): return 1
            
            return dp(i - 1) + dp(i - 2)
        
        return dp(n)