题目描述

有多少种不同的传球方法可以使得从小蛮手里开始传的球，传了m次以后，又回到小蛮手里。两种传球方法被视作不同的方法，当且仅当这两种方法中，接到球的同学按接球顺序组成的序列是不同的。比如有三个同学1号、2号、3号，并假设小蛮为1号，球传了3次回到小蛮手里的方式有1->2->3->1和1->3->2->1，共2种。

思路

这题一看好像可以暴力，但好像会暴，所以机智的选择dp
f[i][j] 表示到第i个人在第j轮时有多少方法，然后dp方程:
f[i][j]=f[i-1][j-1]+f[i+1][j-1]
开头结尾特殊判断一下就可以了
O(nm)

#include 
int f[31][31];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    f[1][0]=1;
    for (int j=1;j<=m;j++)
        for (int i=1;i<=n;i++)
        {
            if (i==1)
                f[i][j]=f[2][j-1]+f[n][j-1];
            else if (i==n)
                f[i][j]=f[1][j-1]+f[n-1][j-1];
            else f[i][j]=f[i-1][j-1]+f[i+1][j-1];
        }
    printf("%d\n",f[1][m]);
}