d212: 東東爬階梯

內容 ：
    東東有個嗜好，爬階梯不是一次走一階，就是一次走兩階。
    換句話說，假設階梯有三階，那他有三種走法
    一：第一步走一階，第二步走二階。
    二：第一步走二階，第二步走一階。
    三：全程都走一階。
    這題要問你，假設階梯有n階，那東東有幾種走法?

輸入說明 ：
    第一行有一個正整數n，0<n<100，表示階梯有n階。

輸出說明 ：
    請輸出n個階梯有幾種走法。

範例輸入 ：
1
2
5

範例輸出 ：
1
2
8

程式碼 ：

#include <stdio.h>

int main() 
{
    int i,n;
    long long arr[101];
    
    arr[1] = 1;
    arr[2] = 2;
    
    for(i=3;i<100;i++)
        arr[i] = arr[i-1] + arr[i-2];
    
    while(scanf("%d",&n)==1)
        printf("%lld\n",arr[n]);
    
    return 0;
}

印出所有情況的程式碼 ：

#include<stdio.h>

int n,map[100];

void DFS(int sum, int step)
{
    if(sum == n)
    {
        for(int i=0; i<step; i++)
            printf("%d",map[i]);
        printf("\n");
        return;
    }
    else if(sum > n)
        return;
    
    map[step] = 1;
    DFS(sum+1, step+1);
    
    map[step] = 2;
    DFS(sum+2, step+1);
}

int main()
{
    int sum, step;
    
    while(scanf("%d",&n)==1)
    {
        sum = 0;
        step = 0;
        DFS(sum, step);
    }
        
    return 0;
}

http://zerojudge.tw/ShowProblem?problemid=d212