题目描述：
工作空闲之余，蒜头君经常带着同事们做游戏，最近蒜头君发明了一个好玩的新游戏：n 位同事围成一个圈，同事 A 手里拿着一个兔妮妮的娃娃。蒜头君喊游戏开始，每位手里拿着娃娃的同事可以选择将娃娃传给左边或者右边的同学，当蒜头君喊游戏结束时，停止传娃娃。此时手里拿着娃娃的同事即是败者。 玩了几轮之后，蒜头君想到一个问题：有多少种不同的方法，使得从同事 A 开始传娃娃，传了 m 次之后又回到了同事 A 手里。两种方法，如果接娃娃的同事不同，或者接娃娃的顺序不同均视为不同的方法。例如 1−>2−>3−>1 和 1−>3−>2−>1 是两种不同的方法。 输入格式 输入一行，输入两个整数 n,m(3≤n≤30,1≤m≤30)，表示一共有 n 位同事一起游戏，一共传 m 次娃娃。 输出格式 输出一行，输出一个整数，表示一共有多少种不同的传娃娃方法。 样例输入 3 3 样例输出 2
解题思路： 我们定义dp[i][j]为传了i次球，此刻球在第j个人的手上。 （1）dp数组的初始化：只传一次球可以把球传到第2个人和第n个人手上，且只有一个办法。所以，dp[1][2]=1;dp[1][n]=1; （2）状态转移方程为：dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1];（要注意第1个人和第n个人特殊一些，具体看代码）
AC代码：
#include <stdlib.h> #include <stdio.h> #include <algorithm> #include <iostream> #include <string.h> #include <math.h> using namespace std; int dp[35][35]; int main() { int n,m,i,j; cin>>n>>m; // dp[i][j]表示传了i次球，现在球在第j个人手上 dp[1][2]=1;//这个步骤（dp数组的初始值）比较难想一些，传一次只能把球传到第2个人或者第n个人手上 dp[1][n]=1; for(i=1;i<=m;i++) { for(j=1;j<=n;j++) { if(j==1) dp[i][j]=dp[i-1][n]+dp[i-1][2]; else if(j==n) dp[i][j]=dp[i-1][n-1]+dp[i-1][1]; else dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1]; } } cout<<dp[m][1]<<endl; return 0; }