looloa @ 2023-03-18 20:32:46

#include<bits/stdc++.h>

using namespace std;

struct step_term{
    int term[1300];  // 高精度存储台阶的存储方法
}steps[5010];  // 这里存储每个台阶

int check_len(int a[]){  // 获取这个数组的位数，感觉问题出在这里
    int i;
    for(i=0;i<1299;i++){
        if(a[i]!=0) break;
    }

    return i;
}

int pluus(int a[], int b[], int pls[]) {  // 高精加法
    for (int i = 1299; i >= min(check_len(a), check_len(b)); i--) {
        pls[i] += a[i] + b[i];
        pls[i - 1] = pls[i] / 10;
        pls[i] %= 10;
    }

    return 0;
}

void output(int a[]){  // 输出
    for(int i=check_len(a);i<=1299;i++){
        cout << a[i];
    }
}

int main(){
    steps[1].term[1299] = 1;
    steps[2].term[1299] = 2;
    check_len(test);
    int n;
    cin >> n;

    if(n==1) {cout << 1; return 0;}
    if(n==2) {cout << 2; return 0;}

    for(int i=3;i<=n;i++){
        pluus(steps[i-1].term, steps[i-2].term, steps[i].term);
    }

    output(steps[n].term);
}

by looloa @ 2023-03-18 20:42:57

慢慢减数组个数搞定了。。。

但还是欢迎各位dalao提出更好的优化算法的方式，本蒟蒻在此非常感谢！！

by Roger_Spencer @ 2023-03-20 09:23:45

高精度+滚动数组+dP

博客主页

源码

#include <bits/stdc++.h>

using namespace std;

#define LL long long

#define endl "\n"

const int N = 1e5 + 10;

const int M = 5510;

int dp[N];

vector<int> add(vector<int> &A, vector<int> &B)
{
    if (A.size() < B.size()) return add(B, A);

    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size(); i ++ )
    {
        t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }

    if (t) C.push_back(t);
    return C;
}

void solve()
{
    int n;
    cin >> n;

    if ( n == 1) 
    {
        cout << 1 << endl;
        return;
    }

    vector<int> A, B, C, D;

    A.push_back(1);
    B.push_back(1);
    for (int i = 2; i <= n; i ++ )
    {
        C = add(A, B);
        A = B;
        B = C;
    }

    for (int i = C.size() - 1; i >= 0; i -- ) cout << C[i];

    cout << endl;

}

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

    solve();

    return 0;
}