COJN 0584 800603吃糖果

800603吃糖果

难度级别：B；运行时间限制：1000ms；运行空间限制：51200KB；代码长度限制：2000000B

试题描述

名名的妈妈从外地出差回来，带了一盒好吃又精美的巧克力给名名（盒内共有 N 块巧克力）。妈妈告诉名名每天可以吃一块或者两块巧克力。假设名名每天都吃巧克力，问名名共有多少种不同的吃完巧克力的方案。例如：如果N=1，则名名第1天就吃掉它，共有1种方案；如果N=2，则名名可以第1天吃1块，第2天吃1块，也可以第1天吃2块，共有2种方案；如果N=3，则名名第1天可以吃1块，剩2块，也可以第1天吃2块剩1块，所以名名共有2+1=3种方案；如果N=4，则名名可以第1天吃1块，剩3块，也可以第1天吃2块，剩2块，共有3+2=5种方案。现在给定N，请你写程序求出名名吃巧克力的方案数目。

输入

输入只有1行，即整数N。

输出

输出只有1行，即名名吃巧克力的方案数。

输入示例

输出示例

其他说明

数据范围：0<N<20.

题解：fibonacci??

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<algorithm>
 5 #include<queue>
 6 #include<cstring>
 7 #define PAU putchar(' ')
 8 #define ENT putchar('
')
 9 using namespace std;
10 const int maxn=20+5;
11 int f[maxn];
12 int dp(int n){
13     if(f[n])return f[n];
14     if(!n||n==1)return 1;
15     if(n==2)return 2;
16     return dp(n-1)+dp(n-2);
17 }
18 inline int read(){
19     int x=0,sig=1;char ch=getchar();
20     for(;!isdigit(ch);ch=getchar())if(ch=='-')sig=0;
21     for(;isdigit(ch);ch=getchar())x=10*x+ch-'0';
22     return sig?x:-x;
23 }
24 inline void write(int x){
25     if(x==0){putchar('0');return;}if(x<0)putchar('-'),x=-x;
26     int len=0,buf[15];while(x)buf[len++]=x%10,x/=10;
27     for(int i=len-1;i>=0;i--)putchar(buf[i]+'0');return;
28 }
29 void init(){
30     int n=read();
31     write(dp(n));
32     return;
33 }
34 void work(){
35     return;
36 }
37 void print(){
38     return;
39 }
40 int main(){init();work();print();return 0;}