TLE 求调玄关

Shawn16 @ 2024-09-19 18:35:58

#include<bits/stdc++.h>
#define int long long
using namespace std;

int dg(int n){
    if(n==1){
        return 1;
    }
    if(n==2){
        return 2;
    }
    return dg(n-1)+dg(n-2);
}
signed main()
{
    int n;
    while(cin>>n){
        cout<<dg(n)<<endl;
    }

    return 0;
}

by jiangyeleia @ 2024-09-19 18:40:02

@Shawn16 一个个递归太麻烦了

#include <bits/stdc++.h>
using namespace std;
int n,len=1,f[5003][5003];
void hp(int k)
{
    int i;
    for(i=1;i<=len;i++)
        f[k][i]=f[k-1][i]+f[k-2][i];
    for(i=1;i<=len;i++)
     if(f[k][i]>=10)
     {
         f[k][i+1]+=f[k][i]/10;
         f[k][i]=f[k][i]%10;
         if(f[k][len+1])len++;
    }
}
int main()
{
    int i;
    scanf("%d",&n);
    f[1][1]=1;
    f[2][1]=2;
    for(i=3;i<=n;i++)
        hp(i);
    for(i=len;i>=1;i--)
        printf("%d",f[n][i]);
    return 0;
}

回关

by lostxxx @ 2024-09-19 18:41:02

换成 dp,一个值比如说dg（1）会被算很多次。

dp[i]=dp[i-1]+dp[i-2];

by Shawn16 @ 2024-09-19 18:41:17

@jiangyeleii 谢谢，已关

by Shawn16 @ 2024-09-19 18:42:46

@lostxxx 本蒟蒻不会dp 但还是关注一下以表感谢

by lostxxx @ 2024-09-19 18:47:08

@Shawn16 其实就是递推