【剣指Offer面接プログラミング問題】テーマ1389:変態ステップ――九度OJ

タイトルの説明:
1匹のカエルは一度に1段の階段を飛び上がることもできるし、2段も飛び上がることもできるし...n段も飛び上がることもできる.このカエルが1つのn級の階段を跳ぶことを求めて全部で何種類の跳び方があります.
入力:
入力には、各テストケースについて、複数のテストケースが含まれる場合があります.
入力は整数n(1<=n<=50)を含む.
出力:
各テストケースに対応し、
出力カエルがn段の階段を飛び上がるのに何種類の飛び方があるのか.
サンプル入力:
6
サンプル出力:
32
【解題構想】本題を手に入れた最初の反応がフィポラチ数列の変種であるが、n段目の飛び方は前のすべての段の飛び方に加算されると考えられるのだろうか.もちろん、この考えは実現できるが、効率は低い.テーマをよく研究すると、多くの繰り返し計算を取り除くことができることがわかります.1段目からn-2段目までのジャンプ法の和は、実はn-1段目のジャンプ法に等しいので、n段目のジャンプ法は、実はn-1段目のジャンプ法の2倍に等しい.アルゴリズムの残りの部分は余計なことではなく,繰返し式が出ており,終了条件も計算しやすい.
AC code:

#include 
#include 
using namespace std;
 
int main()
{
  int n,siz;
  vector vec;
  vec.reserve(52);
  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(2*vec[i-1]);
      }
         
    }
    printf("%lld
",vec[n]);
  }
  return 0;
}
/**************************************************************
    Problem: 1389
    User: huo_yao
    Language: C++
    Result: Accepted
    Time:0 ms
    Memory:1052 kb
****************************************************************/

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