NOIP 2008 普及组 传球游戏「建议收藏」

#include <bits/stdc++.h>
using namespace std;

int n, m, ans;

//第cnt次传球后，球在编号为x的同学手上 
void dfs(int cnt, int x) { 
   
	if (cnt == m) { 
   
		if (x == 0) ans ++;
		return;
	}
	
	dfs(cnt + 1, (x + 1) % n);
	dfs(cnt + 1, (x - 1 + n) % n);	
}

int main() { 
   
	cin >> n >> m;	
	
	//第0次传球，球在编号为0的同学手上 
	dfs(0, 0);
	cout << ans;
	
	return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int N = 40;
int n, m, dp[N][N];

int main() { 
   
	cin >> n >> m;

	//第0次传球在0号同学手中的方法数是1，即初始状态
	dp[0][0] = 1;
	
	//状态转移依赖于上一次传球的状态，所以外循环是1...m
	for (int i = 1; i <= m; i ++) { 
   
		for (int j = 0; j < n; j ++) { 
   
			//dp[i][j]表示第i次传球在j号同学手中的方法数
			dp[i][j] = dp[i - 1][(j + 1) % n] + dp[i - 1][(j - 1 + n) % n];
		}
	}
	cout << dp[m][0] << endl;

	return 0;
}