蓝桥杯算法训练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
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