题解 P1057 【传球游戏】
前言
很多题解都是直接给出状态转移方程的，并没有从维度的角度去分析，所以这篇博客是从维度开始分析的。
Ps：本博客关于维度的分析会借鉴《全新的动态规划入门——从维度谈起》中关于维度的内容，在此感谢原作者独具一格的阐述。以下在括号中注明引用的语句，皆处于上述文章
正题
一、维度
维度其实就是允许某种东西自由变化的范围。（引用）
那么对于本体的状态可以是 球从i->j的方案数，因此我们得到了一个维度f[i] (表示从1号到i号的方案数，显然仅仅一维并不能满足我们的需求)
zhw说：当你的DP不能解决现在的问题时，加一个维度就好了，但是能不能过是另一个问题。（大意如此）
但是题干中还有一个限制条件——传球的次数。为了满足我们的需要，我们可以设f[i][j]为球从1->i传球次数为j次的方案数。
因此，我们关于解决本题的所有需求都已经满足了。
二、状态转移方程
1.状态
事物具有多个维度，反之多个维度就能共同描述一个事物，而多个维度的值就描述了事物的状态。（引用）
由此可知，我们在上文中假设的f[i][j]即为我们需要的状态。
2.状态的转移
DP的状态的转移一般有两种：递推/我为人人，递归/人人为我(间接引用，原句于北大ACM-ICPC暑期课课件)
众所周知，递归极容易爆栈（如果您会手动模拟栈，请无视），所以我们在这里采用一种更为稳妥的方式----递推。
下面我们将探究如何递推。
因为i号点在一个环上,所以有点i-1和点i+1可以向点i转移（可以顺时针穿球，也可以逆时针）。
虽然点i-1，i+1向点i的转移有多种方式，但我们在更新i-1和i+1时已经加入了，所以我们可以得到状态转移方程f[i][j]=f[i-1][j-1][i+1[j-1]。其中当i==n时i-1=1，当i==1时i+1=n。
至此我们已经解决了问题的根本了。
三、枚举的顺序
根据DP的基本定义，我们需要先依次解决传球次数为1，2，3......j的问题
所以我们第一层循环为枚举传球次数。显然，枚举点（人）就需要在第二层循环了。
到这里，全部问题就都解决了。
代码
#include<bits/stdc++.h>
using namespace std;
int n,m;
int f[30][30];
int main()
{
scanf("%d%d",&n,&m);
f[1][0]=f[0][1]=1;
for(int i=1;i<=m;i++)
{
f[1][i]=f[n][i-1]+f[2][i-1];
for(int j=2;j<n;j++)
f[j][i]=f[j-1][i-1]+f[j+1][i-1];
f[n][i]=f[n-1][i-1]+f[1][i-1];
}
printf("%d",f[1][m]);
return 0;
}