YCOJ传娃娃

题目：
传娃娃
Description

学习空闲之余，小信经常带着同学们做游戏，最近小信发明了一个好玩的新游戏：n 位同学围成一个圈，同学 A 手里拿着一个布娃娃。小信喊游戏开始，每位手里拿着娃娃的同学可以选择将娃娃传给左边或者右边的同学，当小信喊游戏结束时，停止传娃娃。此时手里拿着娃娃的同学即是败者。

玩了几轮之后，小信想到一个问题：有多少种不同的方法，使得从同学 A 开始传娃娃，传了 m 次之后又回到了同学 A 手里。两种方法，如果接娃娃的同学不同，或者接娃娃的顺序不同均视为不同的方法。例如 1->2->3->1和 1->3->2->1 是两种不同的方法。

Input

输入一行，输入两个整数 n,m(3≤n≤30,1≤m≤30)，表示一共有 n 位同学一起游戏，一共传 m 次娃娃。

Output

输出一行，输出一个整数，表示一共有多少种不同的传娃娃方法。

Sample Input 1

3 3
Sample Output 1

2

一道简单的DP只要把图画出来了就基本上完成了。

即可推出公式：

dp[i][j]=dp[i][j-1]+dp[i][j+1]//n和1除外

那么dp[0][1]就一定=1。

这样的话，n和1就要特殊处理：

a[i][n]=a[i-1][1]+a[i][n-1];

a[i][1]=a[i-1][2]+a[i][n];

对了如a[i][j]，i表示时间，j表示是哪个人。

代码如下：```cpp

		#include <bits/stdc++.h>
		using namespace std;
		int dp[1000][1000];
		int a[100010];
		int main(){
			int n,m;
			cin>>n>>m; 
			dp[0][1]=1;
			for (int i=1;i<=m;i++){
				for (int j=1;j<=n;j++){
					if (j==n){
						dp[i][j]=dp[i-1][j-1]+dp[i-1][1];
					}else if(j==1){
						dp[i][j]=dp[i-1][j+1]+dp[i-1][n];
					}else {
						dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1];
					}//核心
				}
			}
			cout<<dp[m][1];
			return 0;
		}

现在我们讲解一个样例吧。

如n=3，m=3就有1->2->3->1和 1->3->2->1 两种方法，所以答案就是2。

差不多就是这样了，那就这样结束吧。

$$$$$$$$$$$$$$$$$$END$END$$$$$$$$$$$$$$$$$

标准结尾：