
//高精度 乘以 低精度 
vector<int> add(vector<int> A, int b)
{
    vector<int> res ;
    int t = 0;
    for(int i=0; i<A.size() || t; i++){

        if(i < A.size()) t+=b*A[i];
        res.push_back(t % 10);
        t /=10;
    }

    //res 0 0 0 0 0 
    while(res.size() > 1 && res.back() == 0) res.pop_back();

    return res ;
}

//递归的问题：大量的重复计算！！！ 
long long fib(int n)
{
    if(n <= 2) return 1;
    int a= fib(n-1);
    int b= fib(n-2);
    return a + b; 
}

//用递推来改进递归的问题 
long long f[60] = {0,1,1};
void fibb(int n){
    for(int i=3; i<=n; i++)
    {
        f[i] = f[i-1] + f[i-2];
    }
}

//记忆化+递归 来改进递归的问题 
long long mem[60] = {0}; //记忆力 或者叫备忘录 
long long fibx(int n)
{
    if(n <= 2) {
        mem[n] = 1;
        return mem[n];
    }
    if(mem[n-1] == 0) mem[n-1] = fibx(n-1);
    if(mem[n-2] == 0) mem[n-2] = fibx(n-2);
    mem[n] = mem[n-1] + mem[n-2];
    return mem[n]; 
}



int main(){
    //fibb(50) ;
    cout << fibx(50) ;
    return 0;
}

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com

递归+递推改进+记忆化