hdu1250--Hat's Fibonacci

Problem Description

A Fibonacci sequence is calculated by adding the previous two members the sequence, with the first two members being both 1.
F(1) = 1, F(2) = 1, F(3) = 1,F(4) = 1, F(n>4) = F(n - 1) + F(n-2) + F(n-3) + F(n-4)
Your task is to take a number as input, and print that Fibonacci number.

Input

Each line will contain an integers. Process to end of file.

Output

For each case, output the result in a line.

Sample Input

100

Sample Output

4203968145672990846840663646

这个题在两个时间去做的，第一次是的代码

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 #include <algorithm>
 5 using namespace std;
 6 int dp[8001][2301];
 7 int main()
 8 {
 9     int len,sum;
10     memset(dp,0,sizeof(dp));
11     dp[1][2300]=dp[2][2300]=dp[3][2300]=dp[4][2300]=1;
12     len=1;
13     for(int i=5;i<8001;i++)
14     {
15         sum=0;
16         for(int j=2300;j>2300-len;j--)
17         {
18             sum+=dp[i-1][j]+dp[i-2][j]+dp[i-3][j]+dp[i-4][j];
19             dp[i][j]=sum%10;
20             sum/=10;
21             while(j==2300-len+1&&sum>0)
22             {
23                 dp[i][2300-len]=sum;
24                 len++;
25                 break;
26             }
27         }
28     }
29     int n;
30     while(cin>>n)
31     {
32         int t;
33         for(t=0;t<2300;t++)
34         if(dp[n][t]!=0)
35         break;
36         for(int j=t;j<=2300;j++)
37         cout<<dp[n][j];
38         cout<<endl;
39     }
40     return 0;
41 }

View Code

但是一直（Memory Limit Exceeded）就看了大神的代码

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <vector>
 4 #include <algorithm>
 5 #include <cmath>
 6 #include <string.h>
 7 #include <malloc.h>
 8 using namespace std;
 9 void add(char *a,char *b,char *c)
10 {
11     int i,j,k,t,lmax,lmin,tmp;
12     char *s,*pmax,*pmin;
13     lmax=strlen(a);
14     lmin=strlen(b);
15     if(lmax<lmin)
16     {
17         tmp=lmax;lmax=lmin;lmin=tmp;
18         pmax=b;pmin=a;
19     }
20     else
21     {
22         pmax=a;pmin=b;
23     }
24     s=(char*)malloc(sizeof(char)*(lmax+1));
25     s[0]='0';//注意此处很容易被忽略
26     for(i=lmax-1,j=lmin-1,k=lmax;j>=0;i--,j--,k--)
27         s[k]=pmax[i]-'0'+pmin[j];
28     for(;i>=0;i--,k--)
29     s[k]=pmax[i];
30     for(i=lmax;i>=0;i--)
31     if(s[i]>'9')
32     {
33         s[i]-=10;
34         s[i-1]++;
35     }
36     if(s[0]=='0')
37     {
38         for(i=0;i<=lmax;i++)
39         c[i-1]=s[i];
40         c[i-1]='';
41     }
42     else
43     {
44         for(i=0;i<=lmax;i++)
45         c[i]=s[i];
46         c[i]='';
47     }
48     free(s);
49 }
50 char dp[8001][2301];
51 int main(void)
52 {
53     for(int i=1;i<=4;i++)
54     strcpy(dp[i],"1");
55     for(int i=5;i<8000;i++)
56     {
57         char a[2301],b[2301];
58         add(dp[i-1],dp[i-2],a);
59         add(dp[i-3],dp[i-4],b);
60         add(a,b,dp[i]);
61     }
62     int n;
63     while(cin>>n)
64     {
65         cout<<dp[n]<<endl;
66     }
67     return 0;
68 }

View Code

感觉挺复杂的，不容易明白。

还是想用int数组存，就改进了

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 using namespace std;
 6 int dp[8001][410];
 7 
 8 int main()
 9 {
10     int sum,len;
11     memset(dp,0,sizeof(dp));
12     dp[1][405]=dp[2][405]=dp[3][405]=dp[4][405]=1;
13     len=1;
14     for(int i=5;i<8000;i++)
15     {
16         sum=0;
17         for(int j=405;j>405-len;j--)
18         {
19             sum=sum+dp[i-1][j]+dp[i-2][j]+dp[i-3][j]+dp[i-4][j];
20             dp[i][j]=sum%100000;
21             sum/=100000;
22             while(j==405-len+1&&sum>0)
23             {
24                 dp[i][405-len]=sum;
25                 len++;
26                 break;
27             }
28         }
29     }
30     int n,i;
31     while(~scanf("%d",&n))
32     {
33         for(i=0;i<405;i++)
34         if(dp[n][i]!=0)
35         break;
36         printf("%d",dp[n][i]);
37         for(int j=i+1;j<=405;j++)
38         printf("%05d",dp[n][j]);
39         printf("
");
40     }
41     return 0;
42 }

View Code

这样改一下，感觉一下子就简单了