剣指OFFERの変態階段(九度OJ 1389)

タイトルの説明:

1匹のカエルは一度に1段の階段を飛び上がることもできるし、2段も飛び上がることもできるし...n段も飛び上がることもできる.このカエルが1つのn級の階段を跳ぶことを求めて全部で何種類の跳び方があります.
 

入力:

入力には、各テストケースについて、複数のテストケースが含まれる場合があります.
入力は整数n(1<=n<=50)を含む.
 

出力:

各テストケースに対応し、
出力カエルがn段の階段を飛び上がるのに何種類の飛び方があるのか.
 

サンプル入力:

6 

 

サンプル出力:

32 

問題解決の考え方：

この問題は以前のジャンプステップと大きく異なり,ジャンプステップのステップ数が1からnに変わっただけで,すなわち,ジャンプや2回ジャンプの問題ではなく,n回ジャンプの問題である.問題を解く構想は明らかに逆方向に分析しなければならない.
各最終階段は一歩飛び上がることができて、彼の前の階段から飛び上がることができて、彼の前の2つの階段から2つの階段を飛び上がることができます.では、まとめてみると、
最後に残った階段の数は、前の階段の飛び方を加えればよい.次のようになります.
最後にゼロの階段が残っていて、しばらく0にして、直接nの階段を飛び上がって、明らかに1つの方法しかありません.私たちは循環するたびにまず1を加えればいいです.
最後に1つの階段が残っていると、(n-1番目の階段の方法数)種類が共有される.
最後に2つの階段が残っており、(n-2番目の階段の方法数)種類がある.
　　....
最後にn-1階段が残っていて、1つの方法しかありません.
上記の方法を累積すると,n段目の階段にジャンプする数である.

コード:

 

#include <stdio.h>

long long int arr[51] = {0,1};

void createArr(void);

int main(void){

    int n;

    createArr();

    while(scanf("%d",&n)!=EOF && n>=1 && n<=50){

        printf("%lld
",arr[n]);

    }

    return 0;

}

void createArr(void){

    int i,j;

    for(i=2;i<51;i++){

        j=i-1;

        arr[i]++;// 

        while(j){

            arr[i] += arr[j];

            j--;

        }

    }

}