解题思路

n 个同学围成一圈，球从 1 号（小蛮）手里出发，每次可以传给左边或右边的人，问传 m 次之后球又回到 1 号手里，一共有多少种不同的传法。

这是一道环形动态规划题。

设 dp[step][p] 表示传了 step 次之后，球在 p 号同学手里的方法数。

1. 一开始球在 1 号手里：dp[0][1] = 1
2. 传第 step 次时，球到 p 手里只有两种来源：
   • 上一轮球在 p 的左边那个人手里
   • 上一轮球在 p 的右边那个人手里
3. 所以 dp[step][p] = dp[step-1][左边] + dp[step-1][右边]
4. 因为是围成一圈，1 号的左边是 n 号，n 号的右边是 1 号，要注意处理
5. 最后答案就是 dp[m][1]

举例：3 个人传 3 次回到 1 号，只有两种传法：1→2→3→1 和 1→3→2→1，所以答案是 2。

为什么答案可能很大？ 每传一次都有 2 种选择，m 次最多有 2 的 m 次方种情况，m 最大 30，所以要开 long long 防止溢出。

参考代码

#include <iostream>
using namespace std;

long long dp[35][35];  // dp[step][p] 表示传 step 次后，球在 p 号手里的方法数

int main() {
    int n, m;
    cin >> n >> m;

    dp[0][1] = 1;  // 一开始球在小蛮(1号)手里，算 1 种
    // 一共传 m 次
    for (int step = 1; step <= m; step++) {
        for (int p = 1; p <= n; p++) {
            int left = (p == 1) ? n : p - 1;    // p 左边的人（围成一圈，1 的左边是 n）
            int right = (p == n) ? 1 : p + 1;   // p 右边的人（围成一圈，n 的右边是 1）
            // 这一轮球到 p 手里 = 上一轮从左边的人传过来 + 上一轮从右边的人传过来
            dp[step][p] = dp[step - 1][left] + dp[step - 1][right];
        }
    }

    cout << dp[m][1];  // 传 m 次后又回到 1 号手里的方法数
    return 0;
}

复杂度分析

• 时间复杂度：O(m×n)，两层循环
• 空间复杂度：O(m×n)，一个二维数组