分析
-
动态规划
-
状态表示:
f[i][j]
:表示传了i
次后球位于j
的方案数 -
为了方便处理,这里让
1~n
对应1~n-1
。 -
状态转移:
f[i][j] = f[i - 1][(j - 1 + n) % n] + f[i - 1][(j + 1) % n];
。
代码
#include <iostream>
using namespace std;
const int N = 35;
int n, m;
int f[N][N]; // f[i][j]表示传了i此后球位于j的方案数
int main() {
cin >> n >> m;
f[0][0] = 1;
for (int i = 1; i <= m; i++)
for (int j = 0; j < n; j++)
f[i][j] = f[i - 1][(j - 1 + n) % n] + f[i - 1][(j + 1) % n];
cout << f[m][0] << endl;
return 0;
}