【題解】ZeroJudge d105: NOIP 2008 3.传球游戏

#include <iostream>
#include <cstring>
using namespace std;

int n, m;
//dp[i][j]: 第i次傳球後，球在第j個人手上的方法數目
int dp[31][31];//3<=n<=30，1<=m<=30

int main() {
	while (cin >> n >> m){
		memset(dp, 0, sizeof(dp));
		dp[0][1] = 1; //假設小蛮是第1個人, 一開始球在小蛮手上
		for (int i=1; i<=m; i++){
			for (int j=1; j<=n; j++){
				//n个同学，編號1~n
				int pre_j1 = (j-1 >= 1)? (j-1) : n;
				int pre_j2 = (j+1 <= n)? (j+1) : 1;
				dp[i][j] = dp[i-1][pre_j1] + dp[i-1][pre_j2];
			}
		}
		cout << dp[m][1] << '\n';
	}
    return 0;
}

while True:
	try:
		n, m = map(int, input().split())
		#dp[i][j]: 第i次傳球後，球在第j個人手上的方法數目
		dp = [[0 for i in range(n+1)] for j in range(m+1)]
		# 假設小蛮是第1個人, 一開始球在小蛮手上
		dp[0][1] = 1
		for i in range(1, m+1):
			for j in range(1, n+1):
				if j-1 >= 1:
					pre_j1 = j - 1
				else:
					pre_j1 = n
					
				if j+1 <= n:
					pre_j2 = j + 1
				else:
					pre_j2 = 1
					
				dp[i][j] = dp[i-1][pre_j1] + dp[i-1][pre_j2]
				
		print(dp[m][1])
	except:
		break