動態規劃經典：圓圈傳球游戲 — 狀態轉移與邊界處理全解析

編輯：關於C語言

問題描述

n 個同學圍成一圈（編號 1~n，小蠻為 1 號），球從 1 號開始傳，每次只能傳給左右相鄰同學。傳 m 次後球回到 1 號手中。求不同傳球方法數。兩種方法不同 ⇔ 接球序列不同。

約束條件

3 ≤ n ≤ 30, 1 ≤ m ≤ 30
多組測試用例，EOF 結束

樣例

輸入: 3 3
輸出: 2
解釋: 1→2→3→1 和 1→3→2→1

動態規劃建模

狀態定義

dp[i][j]：第 j 次傳球結束後，球恰好在 i 號手中的方法數

1 ≤ i ≤ n, 0 ≤ j ≤ m
初始狀態：dp[1][0] = 1（0 次傳球，球在 1 號）

狀態轉移方程

第 j 次傳球到 i，必來自第 j-1 次在左右鄰居：

dp[i][j] = dp[left(i)][j-1] + dp[right(i)][j-1]

其中：

left(i) = (i == 1) ? n : i-1
right(i) = (i == n) ? 1 : i+1

邊界處理（環狀結構關鍵）

// 通用寫法：模運算統一處理環狀索引
int left = (i - 2 + n) % n + 1;  // 1-based 索引左鄰居
int right = i % n + 1;           // 1-based 索引右鄰居
dp[i][j] = dp[left][j-1] + dp[right][j-1];

完整代碼實現（C++17）

#include 
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    while (cin >> n >> m) {
        // dp[i][j]: 第 j 次傳球後球在 i 號手中的方案數
        vector> dp(n + 1, vector(m + 1, 0));
        dp[1][0] = 1; // 初始：0 次傳球，球在 1 號

        for (int j = 1; j <= m; ++j) {
            for (int i = 1; i <= n; ++i) {
                int left = (i - 2 + n) % n + 1;
                int right = i % n + 1;
                dp[i][j] = dp[left][j-1] + dp[right][j-1];
            }
        }
        cout << dp[1][m] << '\n';
    }
    return 0;
}

空間優化：滾動數組 O(n)

第 j 步只依賴 j-1 步，可壓縮為兩個一維數組：

vector prev(n+1), curr(n+1);
prev[1] = 1;
for (int step = 1; step <= m; ++step) {
    fill(curr.begin(), curr.end(), 0);
    for (int i = 1; i <= n; ++i) {
        int left = (i - 2 + n) % n + 1;
        int right = i % n + 1;
        curr[i] = prev[left] + prev[right];
    }
    swap(prev, curr);
}
cout << prev[1] << '\n';