蒜头君的新游戏

题目:


代码如下：

#include<bits/stdc++.h>
using namespace std;
int dp[35][35];
int main()
{
	int n,m;
	cin >> n >> m;
	dp[0][1] = 1;	//dp[i][j]代表传i次娃娃的时候最后回到j手上的可能方案数 
	for(int i = 1;i <= m;i++){
		for(int j = 1;j <= n;j++){
			if(j == 1) dp[i][j] = dp[i - 1][n] + dp[i - 1][2];	//传达第1个人手中有两条路，一条是从2传过来，第二条是从n传过来
			else if(j == n) dp[i][j] = dp[i - 1][n - 1] + dp[i - 1][1]; //传达第n个人手中有两条路，一条是从1传过来，第二条是从n - 1传过来
			else dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1];//不在头尾的情况 
		}	
	} 
	cout << dp[m][1] << endl;
	return 0;
} 

这是一道dp题，想清楚状态和转移方程就不难，上面代码有注释。