传球游戏

题意：

n个同学围成一个圆圈进行传球游戏，一个同学传球时只能传给左右的同学，传m次最终回到第一个人手里，问你有多少种情况？

思路：

第一步：确定状态——原问题是什么，子问题是什么？

• 原问题：从1开始传球，第m步回到1号的情况数
• 子问题：从1开始传球第i步到达j号的情况数
• dp[i] [j]表示第i次传球后在j位置的情况数

第二步：确定状态转移方程和边界

• dp[i] [j] = dp[i - 1] [j - 1] + dp[i - 1] [j + 1]

• dp[0] [1] = 1 ，初始条件一号开始的时候是1

• 是个环，需要对边界1和m进行讨论

  #include <cstdio>
  #include <cstring>
  #include <string>
  #include <cmath>
  #include <iostream>
  #include <algorithm>
  #include <vector>
  #include <stack>
  #include <queue>
  #include <stdlib.h>
  #include <sstream>
  #include <map>
  #include <set>
  using  namespace std;
  #define inf 0x3f3f3f3f
  #define MAX 1000000 + 7
  #define endl '\n'
  #define mod 1e9+7;
  typedef  long long ll ;
  //不开longlong见祖宗！
  //ios::sync_with_stdio(false);
  //cin.tie(0); cout.tie(0);
  inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;
          ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
  
  int n, m;
  int dp[100][100];
  
  int main(){
      cin>>n>>m;
      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][j + 1] + dp[i - 1][n];
          }
          else if(j == n){
              dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][1];
          }
          else dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1];
      }
      cout<<dp[m][1]<<endl;
  }