这是一个经典的动态规划问题,我们可以定义一个二维数组dp[i][j],其中i表示传球的次数,j表示球当前在哪个同学手里。我们需要找到的是dp[m][1],即球传了m次后又回到1号同学手里的方法数。
我们可以从1次开始,逐次计算每个dp[i][j]的值。对于每个dp[i][j],它的值等于dp[i-1][j-1]和dp[i-1][j+1]的和,因为球可以从j-1号同学传到j号同学,也可以从j+1号同学传到j号同学。注意这里需要处理一下边界情况,即当j=1时,j-1应该等于n,当j=n时,j+1应该等于1。
下面是对应的C++代码:
#include <iostream>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
int dp[35][35] = {0};
dp[0][1] = 1;
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];
} else if (j == n) {
dp[i][j] = dp[i-1][n-1] + dp[i-1][1];
} else {
dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1];
}
}
}
cout << dp[m][1] << endl;
return 0;
}
这段代码首先读入n和m的值,然后初始化dp数组,其中dp[0][1]的值为1,表示球在开始时就在1号同学手里。然后通过两层循环,逐次计算每个dp[i][j]的值。最后输出dp[m][1]的值,即球传了m次后又回到1号同学手里的方法数。