#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <functional>
#include <list>
#include <map>
#include <set>
using namespace std;

long array[50][2];


class POJ     
{
  public:
  int POJMethod()
  {
    array[1][1] = 1;
    array[1][0] = 1;
    for(int i = 2;i<=49;++i)
    {
      array[i][0] = array[i-1][0] + array[i-1][1];
      array[i][1] = array[i-1][0];        
    }
    return 0;
  }
};


int main()
{     
    int n,Scenario;
    cin>>n;
    int temp = n;
    POJ  test;
    test.POJMethod();
    
    while(temp--)
    {
      cin>>Scenario;
      printf("Scenario #%d:\n%d\n\n",n-temp,array[Scenario][1]+array[Scenario][0]);

    }

    system("pause");
    return 0;
};


比较简单的DP，希望能对您有帮助