蓝桥杯算法训练VIP-传球游戏

题目

题目链接

题解

动态规划。

这个题不能用DFS，用DFS的小朋友趁早放弃，输入数据为30 30时，输出为155117522，这就意味着要是dfs的话，需要搜到底155117522次，光遍历这么多次都会超时更别说深搜了，所以只能动归。

也算比较经典的dp之一了。
dp[i][j]表示经过j次传球，球最后回到第i个人手中的方案数；
转移方程：dp[i][j] = dp[i-1][j-1] + dp[i+1][j-1]
含义为：第j次传球要么是第i个人的左手边的人传过来的，要么是右手边，对应着i+1和i-1；
我们应当注意取模，即最终转移方程为dp[i][j] = dp[(i+n-1)%n][j-1] + dp[(i+1)%n][j-1]
初始化为dp[0][0] = 1， 表示0号传0次球回到0号手里的方案数，这里的0号对应题目中的第一个小朋友。

因为我定义的dp数组的第一维表示小朋友，第二维表示传球次数，因此外层循环为第二维，内层为第一维。其实我们也可以根据递推方程得知要先循环第二维，因为没计算出i+1的信息就没法得到第i个的信息，显然不能先循环第一维吧。

代码

#include<bits/stdc++.h>
using namespace std;
int n, m, dp[50][50];

int main()
{
	cin>>n>>m;
	
	dp[0][0] = 1; // 0号传0次球回到0号手里的方案数 
	for(int j = 1;j <= m;j ++)
	for(int i = 0;i < n;i ++)
	dp[i][j] = dp[(i+n-1)%n][j-1] + dp[(i+1)%n][j-1];	

	cout << dp[0][m] << endl;
	return 0;
}