题解 | #传球游戏#

• 题目考点：线性dp
• 题目大意：n个小牛♂牛围成一圈传球，问传球m次传回第一个人的情况有几种
• 题目分析：dp[ i ][ j ] 表示i次传球后，球在第j个人手里的情况，可以想到传球给这个人手里的是他左边的那个人（j-1）或者他右边那个人（j + 1 ）
  因此dp[ i ][ j ] = dp [ i - 1 ][ j - 1 ] + dp [ i - 1] [ j + 1 ]
  初始化dp[ 0 ] [ 1 ] = 1表示0次传球传给第一个人的情况只有一种

#include<iostream>
#include<algorith>

using namespace std;

int n, m, dp[35][35], la, ne;
int main()
{
    dp[0][1] = 1;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; i++)
        for(int j = 1; j <= n; j++){
            la = j == 1 ? n : j-1;  //当成一个圈处理
            ne = j == n ? 1 : j+1;
            dp[i][j] = dp[i-1][la]+dp[i-1][ne];
        }
    printf("%d", dp[m][1]);
    return 0;
}