题解 | 斐波那契数列

#include <iostream>
#include <vector>
using namespace std;

// 记忆化递归写法
long long fiboMemo(int n, vector<long long>& memo) {
    if (memo[n] != -1)
        return memo[n];
    // 递推
    memo[n] = fiboMemo(n - 1, memo) + fiboMemo(n - 2, memo);
    return memo[n];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int input;
    if (!(cin >> input) || input < 1) {
        cout << "Invalid input\n";
        return 0;
    }
    // 根据最大可能的 input 调整 size
    vector<long long> memo(input + 1, -1);
    memo[1] = memo[2] = 1;  // 基例

    // 方法一：记忆化递归
    long long ans1 = fiboMemo(input, memo);
    cout << ans1 << "\n";

    return 0;
}

感觉还是这种中间派方法更好理解