洛谷 P1057 传球游戏（背包DP）

题目大意：

有n个人围成一圈，每个人可以把手上的球传给左边或者右边，现在小明开始传球，问m次后，把球传回给自己的次数。

解题思路：

考虑DP，使用带记忆的DP， 首先我们的状态可以设为[还剩的传球次数][到谁手里了]，转移方程为

本人拿到的球返回小明的次数=右边那位小朋友拿到的球返回给小明的次数 + 右边那位小朋友拿到的球返回给小明的次数

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXT=40;
const int MAXP=40;
int memo[MAXT][MAXP];
int n,m;
int dfs(int time,int peo){
  if(!time && !peo)return 1;
  if(!time)return 0;
  if(memo[time][peo]!=-1)return memo[time][peo];
  const int dx[]={-1,1};
  int times=0;
  for(int i=0;i<2;i++){
    int nxpeo=(peo+dx[i])%n;
    times+=dfs(time-1,nxpeo);
  }
  return memo[time][peo]=times;
}
int32_t main(){
  cin>>n>>m;
  memset(memo,-1,sizeof(memo));
  int ans=dfs(m,0);
  cout<<ans<<endl;
  return 0;
}