【剣指Offer面接プログラミング問題】テーマ1388:階段を跳ぶ--九度OJ

タイトルの説明:
1匹のカエルは一度に1段の階段を飛び上がることも、2段を飛び上がることもできます.このカエルが1つのn級の階段を跳ぶことを求めて全部で何種類の跳び方があります.
入力:
入力には、各テストケースについて、複数のテストケースが含まれる場合があります.
入力は整数n(1<=n<=70)を含む.
出力:
各テストケースに対応し、
出力カエルがn段の階段を飛び上がるのに何種類の飛び方があるのか.
サンプル入力:
5
サンプル出力:
8
【解題の考え方】問題は正面から突破するのは難しいので、角度を変えて考えることができます.n番目の階段を跳ぶにはいくつかの跳び方がありますか.第n−1ステップからジャンプするステップと第n−2ステップからジャンプするステップの2つがある.従って,n番目のステップのジャンプ法がn−1番目のステップのジャンプ法+n−2番目のステップのジャンプ法に等しいことが自然に得られる.これはフィポラチ数列に似ているのではないでしょうか.そうすれば、万能の再帰解法をすぐに考えることができます.再帰的な終端条件は,n=0とn=1のとき,いくつかのジャンプ法があることをすぐに知ることができることである.
AC code:

#include 
#include 
using namespace std;
 
int main()
{
  int n,siz;
  vector vec;
  vec.reserve(72);
  vec.push_back(1);
  vec.push_back(1);
  while(scanf("%d",&n)!=EOF)
  {
    if(n>=vec.size())
    {
      siz=vec.size();
      for(int i=siz;i<=n;++i)
        vec.push_back(vec[i-1]+vec[i-2]);
    }
    printf("%ld
",vec[n]);
  }
  return 0;
}
/**************************************************************
    Problem: 1388
    User: huo_yao
    Language: C++
    Result: Accepted
    Time:0 ms
    Memory:1052 kb
****************************************************************/

タイトルリンク:http://ac.jobdu.com/problem.php?pid=1388