NC16619 传球游戏

题目要求在m次传球之后传到1号位的方案
我们可以定义状态在第i次传球之后在j号位的方案，即dp[i][j]的含义
状态转移方程就是dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1] 即第i次传球之后再j位置上的方案数等于第i-1次传球在j-1和j+1位置上的方案数，注意j=1和j=n的情况要特判

#include <iostream>
using namespace std;
const int maxn = 35;
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][j] = dp[i - 1][n] + dp[i - 1][j + 1];
            else if (j == n)dp[i][j] = dp[i - 1][n - 1] + dp[i - 1][1];
            else dp[i][j] += dp[i - 1][j - 1]+dp[i-1][j+1];
            //cout << "dp[" << i << "][" << j << "]=" << dp[i][j] << endl;
        }
    }
    cout << dp[m][1];
}