조합 수 타 표 법 (1587: 계단 오 르 기)

이 문 제 는 사고 방향 이 비교적 뚜렷 하고 사용 하 는 방법 은 조합 수 타 표 법 이다.http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1587
(1587: 계단 오 르 기)

#include <iostream>

#define max 46

using namespace std;



long long c[max][max];

int main()

{

    for(int i = 0;i < max;i++){

        c[i][0]=1;

        c[i][i]=1;

    }

    for(int i = 1;i < max;i++){

        for(int j = 1;j < i;j++){

            c[i][j]=c[i-1][j] + c[i-1][j-1];

        }

    }

    /*

    for(int i = 0;i < max;i++){

        for(int j = 0;j < max;j++){

            cout<<c[i][j]<<" ";

        }

        cout<<endl;

    }

    */

    int t,z;

    cin>>t;

    while(t--){

        cin>>z;

        int m = z/2;

        long long count=0;

        //              

        for(int i = 0;i <= m;i++)

        {

            count+=c[z-i][i];

        }

        cout<<count<<endl;



    }

    return 0;

}