嗨，大家好，今天想跟大家分享一下d105. NOIP 2008 3.传球游戏 這一題的解題想法，歡迎大家一起討論

我的C++程式碼

#include <bits/stdc++.h>
using namespace std;
#define N 32
int n,m;
int dp[N][N];

int main(){
  cin>>n>>m;
  dp[0][1]=1;
  for(int i=1;i<=m;i++){
    for(int j=1;j<=n;j++){
      int left,right;
      if(j==1) left=n;
      else left=j-1;
      if(j==n) right=1;
      else right=j+1;
      dp[i][j]=dp[i-1][left]+dp[i-1][right];
    }
  }
  cout<<dp[m][1]<<endl;
}

接著來說一下我的解題思路

1. 首先我設了一個動態規劃的陣列dp，其中dp的功能:
dp[傳了幾次][目前位置] = 有幾種方式
換句話說，dp[i][p] 代表傳了 i 次球後，球剛好在 p 號位置的方法數。

2. 然後我把問題簡化，現在我想知道我是怎麼走到 dp[x][y]這一格的，有兩種可能，一種是從y的左邊，往右走一個到y，傳球次數+1 ，或是 y的右邊，往左走一個到y，傳球次數+1 。所以我們可以推出狀態轉移方程 : dp[x][y]=dp[x-1][y的左邊]+ dp[x-1][y的右邊]

3. 接下來我們要處理基底條件(就像一個遞迴數列的開頭)，如果沒有它，狀態轉移方程會沒辦法算出正確答案
`dp[0][n] =1 ; //只有一種方式能在傳了0次時在原位`

4. 最後輸出 選了m次後在位置1(也就是回到原位)時的方法次數就大功告成啦
`cout<<dp[m][1]<<endl;`

在實作時需要注意的事項:
1. 題目中有說道，遊戲規則是所有人圍成一個圓圈，假設今天有1,2,3,4,5個人圍成圓圈，那麼這時候5號位置的右邊那位是1號位置，而1號位置的人左邊是5號位置，所以在寫的時候要記得確保圓環的結構喔