Constraints

Time Limit: 1 secs, Memory Limit: 32 MB

Description

上體育課的時候，小蠻的老師經常帶著同學們一起做游戲。這次，老師帶著同學們一起做傳球游戲。

游戲規則是這樣的：n個同學站成一個圓圈，其中的一個同學手裡拿著一個球，當老師吹哨子時開始傳球，每個同學可以把球傳給自己左右的兩個同學中的一個左右任意），當老師再次吹哨子時，傳球停止，此時，拿著球沒傳出去的那個同學就是敗者，要給大家表演一個節目。

聰明的小蠻提出一個有趣的問題：有多少種不同的傳球方法可以使得從小蠻手裡開始傳的球，傳了m次以後，又回到小蠻手裡。兩種傳球的方法被視作不同的方法，當且僅當這兩種方法中，接到球的同學按接球順序組成的序列是不同的。比如有3個同學1號、2號、3號，並假設小蠻為1號，球傳了3次回到小蠻手裡的方式有1->2->3->1和1->3->2->1，共2種。

Input

輸入有多組Case,每Case一行，有兩個用空格隔開的整數n，m3<=n<=30，1<=m<=30）。

Output

每組Case輸出一行，有一個整數，表示符合題意的方法數。

Sample Input

3 3

Sample Output

2

動態規劃遞歸）

設dp[i][j]為第j次傳球後恰好到第i個人手上的方案數，則易得轉移方程：

dp[i][j]=d[i-1][j-1]+dp[i+1][j-1]

另外由於人圍成一個圈，所以有特殊情況：

dp[1][j]=dp[2][j-1]+dp[n][j-1]

dp[n][j]=dp[n-1][j-1]+dp[1][j-1]

代碼如下：

#include<iostream>
#include<cstring>
using namespace std;
int main()
{
    int n,m;
    while(cin>>n>>m){
        int dp[31][31];
        memset(dp,0,sizeof(dp));
        dp[2][1]=1;
        dp[n][1]=1;
        //dp[i][j]:j次傳球恰好到i
        for(int j=2;j<=m;j++){
                for(int i=1;i<=n;i++){
                        if(i==1)
                        dp[i][j]=dp[i+1][j-1]+dp[n][j-1];
                        else if(i==n)
                        dp[i][j]=dp[i-1][j-1]+dp[1][j-1];
                        else
                        dp[i][j]=dp[i-1][j-1]+dp[i+1][j-1];
                        }
                }
        cout<<dp[1][m]<<endl;
        }
        //system("pause");
        return 0;
        }