NOIP 传球游戏

这题的思想是：传到每个人的可能情况a[i,j]:=a[i-1,j]+a[i-1,j+1](1，n特殊考虑）

i:传球的次数 j:球从谁的手里过来

因为求可能从左边传过来，也可能从右边传过来，将两种情况相加即可

对递推式的解释：

设a[i,j]表示从小蛮开始传了i次后到第j个人手里的方法数，由于球能向两边传，所以

只有当传了i-1次时且球在与第j个人相邻的两个人之一手中，下一次（即第i次）才能传到j手中。

由此得到递推式：
a[i,j]=a[i-1,j-1]+a[i-1,j+1] 1<j<n
a[i-1,n]+a[i-1,j+1] j=1
a[i-1,j-1]+a[i-1,1] j=n
初始时a[1,2]=1 a[1,n]=1 因为只传一次时球只能传到第2个人和最后一个人手中,

也可以只初始化a[0,1]，表示第0次时球在小蛮手里，计数1

program p1485;
var a:array[0..30,0..30]of longint;
i,j:integer;
m,n:integer;
begin
readln(n,m);
a[0,1]:=1;
for i:=1 to m do
for j:=1 to n do
if j=1 then a[i,j]:=a[i-1,n]+a[i-1,2]
else
if j=n then a[i,j]:=a[i-1,1]+a[i-1,n-1]
else a[i,j]:=a[i-1,j-1]+a[i-1,j+1];
writeln(a[m,1]);
readln;
end.

此题我是用递推做的，其实事后细想这也应该属于动态规划。可以设[b]f[i][j][/b]为第i次传到第j个人