两种代码的对比

第一种递归：超时50%

#include<bits/stdc++.h>

using namespace std;

int muniu_num(int n)

{

if(n<=3)

return n;

return muniu_num(n-1)+muniu_num(n-3);

}

int main()

{

int n,k;

cin>>n;

while(n!=0)

{

k=muniu_num(n);

cout<<k<<endl;

cin>>n;

}

}

第二种:不超时

#include<bits/stdc++.h>

using namespace std;

int a[60];

int main()

{

int n;

a[1]=1;

a[2]=2;

a[3]=3;

for(int i=4;i<55;i++)

{

a[i]=a[i-1]+a[i-3];

}

cin>>n;

while(n!=0)

{

cout<<a[n]<<endl;

cin>>n;

}

}