『题解』A10.传球游戏

前言：建议升黄/普及

#include <bits/stdc++.h>
using namespace std; 
const int maxn=5005; 
int dp[maxn][maxn]; 
int main(){ 
	int n,m; 
	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][1]+=dp[i-1][2]+dp[i-1][n]; 
			}
			else if(j==n){
				dp[i][n]+=dp[i-1][1]+dp[i-1][n-1]; 
			}
			else{
				dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1];
			} 
		}
	}
	cout<<dp[m][1]<<endl;
	return 0; 
}