1763. 传球游戏

TAG 动态规划

设f[i][j] 为传 i 次，传到同学 j 有多少种方法。（小蛮编号为0）。

f[i][j] = f[i-1][ (j+1)%n ]+ f[i-1][ (j+n-1)%n ] ，即由相邻的同学再传一次，便能到达 j 手中。

#include <stdio.h>
#include <memory.h>
int dp[31][30];
int n,m;
int main(int argc, char *argv[])
{
	while ( scanf("%d%d", &n, &m)!=EOF )
	{
		memset(dp, 0, sizeof(dp));
		dp[0][0]=1;
		for (int i=1; i<=m; ++i)
		{
			for (int j=0; j<n; ++j)
			{
				dp[i][j]=dp[i-1][(j+1)%n]+dp[i-1][(j+n-1)%n];
			}
		}
		printf("%d/n",dp[m][0] );
	}
	return 0;
}