Python题解

def fibonacci_dp(n, cache={}):
    if n == 0:
        return 0
    if n == 1 or n == 2:
        return 1
    if n in cache:
        return cache[n]
    else:
        cache[n] = fibonacci_dp(n -1 , cache) + fibonacci_dp(n - 2, cache)
    return cache[n]
result = 0
n  = int(input())
for i in range(n+1):
    result = fibonacci_dp(i)
print(result)