9度OJ 1389剣指offer面接問題9変形:変態階段

タイトルの説明
1匹のカエルは一度に1段の階段を飛び上がることもできるし、2段も飛び上がることもできるし...n段も飛び上がることもできる.このカエルが1つのn級の階段を跳ぶことを求めて全部で何種類の跳び方があります.
入力
入力には複数のテストサンプルが含まれる場合があり、各テストケースについて、入力には整数n(1<=n<=50)が含まれる.
しゅつりょく
各テストケースに対応して、カエルがn段の階段を飛び上がるのに合計何種類のジャンプ法があるかを出力します.
サンプル入力
6
サンプル出力
32

問題を解く構想.

要求されたn段の階段を飛び上がるにはいくつかの方法がf(n)であると仮定すると、カエルは1～n歩跳ぶことができるため、最後のステップが1段の階段を跳ぶと、すなわちn-1段を跳んだ後にこの段の階段を跳ぶとよい.最後のステップが2段の階段を跳ぶと、n-2段の階段を跳んだ後、この2段の階段を跳ぶと、f(n-2)種類の跳躍法がある.同様に、最後のステップ3段ジャンプにはf(n-3)種のジャンプ法がある......最後のステップn段ジャンプにはf(n-n)すなわちf(0)すなわち1種のジャンプ法がある.したがって、

f(n) = f(n-1) + f(n-2) + ... + f(1) + f(0)    ........ (1)

このうち、f(0)=f(1)=1であるため、本題にはサボる書き方があり、直接f(n)=2^(n-1)で計算結果を算出すればよい.式(1)でプログラミングする場合は、次の2点に注意してください.

の間には多くの繰り返し計算があるので、効率を向上させるために各ステップの計算結果

を1つの配列で格納する.

計算結果はint型が範囲外になるとwrong answerになるのでlong long型を使用します.

コードは次のとおりです。

//
//  main.cpp
//  offer9-2
//
//  Created by YitongFeng on 7/17/15.
//  Copyright (c) 2015 yetong. All rights reserved.
//

#include 
using namespace std;
long long result[52]; 
//#define debug

class Solution{
public:
    long long frog_jump(int n){
        result[0] = 1;
        long long ways = 0;
        if(n == 0)  ways = 1;
        for(int i = 0; i < n; i++){
            ways += result[i];
            result[i+1] = ways;
#ifdef debug
            cout << "result" << i << " " << result[i] <#endif

        }

        return result[n];
    }
};

int main(int argc, const char * argv[]) {
    int n;
    while(cin >> n){
        if(n > 0){
            Solution s;
            cout << s.frog_jump(n) << endl;
        }
    }

    return 0;
}

/**************************************************************
    Problem: 1389
    User: *******
    Language: C++
    Result: Accepted
    Time:10 ms
    Memory:1520 kb
****************************************************************/