传球游戏 题解

肥肠 简单 的一道题！
当你使用久经沙场的暴搜DFS时！
你会喜提70pts，得出三个TLE超1秒的检测点...
TLEの记录
但你如果用上 记忆化DFS DP...
AC代码：

#include<bits/stdc++.h>
using namespace std;
int n,m;//一共n个人，传m次 
可以得出结论 位置相同，步数相同的时候解都会一样,即处在同一时空内的步数可以记忆化存储，在DFS到相同时空的时候直接输出
int vis[40][40];//标记当前处于同一时空内是否传过该位置 
int dp[40][40];//记忆化数组  dp[now][step]=dp[next][step+1]+dp[pre][step+1]
void dfs(int now,int step){//当前编号,步数
	vis[now][step]=1; 
	//cout<<now<<' '<<step<<endl;
	if(step==m&&now==1){
		//cout<<"成功"<<now<<' '<<step<<endl;
		dp[now][step]+=1;return ;
	}
	else if(step==m){return ;}
	int next=now+1;//传给下一个人 
	if(next>n) next=1;
	int pre=now-1; //传给上一个人 
	if(pre<1) pre=n;
	//如果下一步没有走过，预处理 
	if(!vis[next][step+1]) dfs(next,step+1);
	if(!vis[pre][step+1]) dfs(pre,step+1);
	//否则直接查找dp,存储结果 
	dp[now][step]=dp[next][step+1]+dp[pre][step+1];
    状态转移：当前位置的解=下一步传给上一个人的解+下一步传给下一个人的解
}
int main() {
	cin>>n>>m;
	if(n%2==0&&m%2==1){cout<<0;return 0;}//偶数个人，奇数传球次数时球必回不到1 
	dfs(1,0);
    cout<<dp[1][0];
	return 0;
}