P1057 传球游戏

P1057 传球游戏

#include <bits/stdc++.h>
using namespace std;
int n,m;

int dp[40][40];
int main(){
    //freopen("in","r",stdin);
    ios::sync_with_stdio(0);
    cin >> n >> m;
    dp[0][1] = 1;//表示传球0次给1需要的方法数
    dp[1][2] = 1;//表示传球1次给2需要的方法数
    dp[1][n] = 1;//表示传球1次给n需要的方法数
    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];//1只能由n或者2给他
            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;
}