传球游戏

解题思路

我们可以设f(i,j)为传i秒后，球在j号的方法数
因为0秒时球在1号，所以初值为f(0,1)=1
因为球只能从左右传来，所以递推式为
f [ i ] [ j ] = f [ i − 1 ] [ j − 1 ] + f [ i − 1 ] [ j + 1 ] f[i][j]=f[i-1][j-1]+f[i-1][j+1] f[i][j]=f[i−1][j−1]+f[i−1][j+1]
但又因为他们围成一个圆，所以1和n的传球方式特殊点

AC代码

#include<cstdio>
using namespace std;
int n,m,f[35][35];
int main()
{
   
	scanf("%d%d",&n,&m);
	f[0][1]=1;//初值
 	for(int i=1;i<=m;i++)//递推
	 for(int j=1;j<=n;j++)
 	  if(j==1)f[i][j]=f[i-1][n]+f[i-1][j+1];
 	  else if(j==n)f[i][j]=f[i-1][j-1]+f[i-1][1];
 	  else f[i][j]=f[i-1][j-1]+f[i-1][j+1];
	printf("%d",f[m][1]);
	return 0;
}

谢谢