#include<iostream>

using namespace std;

int f(int N)

{

if(N==1)

return 1;

if(N==2)

return 2;

if(N>=3)

return f(N-1)+f(N-2);       /*發現後面答案都是f(N-1)和f(N-2)的結果相加*/

}

int main(void)

{

int N;

while(cin>>N)

cout<<f(N)<<endl;

return 0;

}

#include

using namespace std;

 

int f(int N)

{

if(N==1)

return 1;

if(N==2)

return 2;

if(N>=3)

return f(N-1)+f(N-2);       /*發現後面答案都是f(N-1)和f(N-2)的結果相加*/

}

 

int main(void)

{

int N;

 

while(cin>>N)

cout<<f(N)<<endl;

 

return 0;

}

 

時間複雜度O(2^n)

你跑 N=100 試試看

他會算到天荒地老

用DP 只有 時間複雜度只有 O(n)

DP大概像這樣

#include<cstdio>
main(){
    int a,b,n;
    while(~scanf("%d",&n)){
        a=b=1;
        while(n--)
            a=(b+=a)-a;
        printf("%d\n",a);
    }
}