骚操作解法：装饰器以及正经的C++解法

一个很骚的py解法，上代码：

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(k):
    if k == 1 or k == 2:
        return 1
    return fib(k-1) + fib(k-2)

n = int(input())
print(fib(n))

正常的C++

#include <iostream>
using namespace std;
long long f[69];
long long dfs(int x) {
	if (f[x]) {
		return f[x];
	}
	if (x <= 2) {
		return f[x] = 1;
	}
	return f[x] = dfs(x - 1) + dfs(x - 2);
}
int main() {
	int n;
	cin >> n;
	cout << dfs(n);
    return 0;
}

因为斐波那契数列不可能有0，所以以if (f[x])可以直接判断有没有存过，存过直接用，没有就存一个，可以大幅度减少重复，python这个就是@lru_cache(maxsize=None)这个超糖语法直接给他了无上限缓存来存这些已经算过的，没算的就存进去，逻辑是类似的