蓝桥杯算法训练1610-传球游戏-JAVA题解（带图详细解析动态规划——小白向）

解题思路:

首先我们以题目的三人传球为例，每个人只能传给自己左右的人，如下图所示：

在编程的时候，我们把学生序列存储为数组，小蛮在第一个，也就是0位置，数组形式的传球如下图所示：

每轮传球，球传到序号x的学生手中的可能应该是上一轮传球中他左、右两侧同学拥有球的可能性之和，以3人为例就如下图所示：

 这部分图解还是看不懂的同学，可以再查阅一下“动态规划”的讲解

代码实现：

题目给的n表示学生数量，m表示轮数

但在构建二维数组的时候，应该构建的事a[m+1][n]，因为初始状态不算在传递轮数中

然后就是a[i][j]等于多少了，这里要分情况讨论：

我们把圈拆成了数组，因此首、尾需要不同的处理方式表示其左右的同学，具体详见如下代码：

for(int i=1;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(j==0) //第一个同学
{
a[i][j]=a[i-1][1]+a[i-1][n-1];
}
else if(j==n-1) //最后一个同学
{
a[i][j]=a[i-1][0]+a[i-1][n-2];
}
else //中间的同学
{
a[i][j]=a[i-1][j-1]+a[i-1][j+1];
}
}
}

参考代码:

import java.util.Scanner;

public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n=scan.nextInt();
int m=scan.nextInt();
m++;
int [][]a=new int[m][n]; //存储第m轮各同学拿到球的可能性

for(int i=1;i<m;i++) //二维数组初始化
{
for(int j=0;j<n;j++)
{
a[i][j]=0;
}
}
a[0][0]=1; //小蛮初始就拿到了球
for(int i=1;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(j==0) //第一个同学
{
a[i][j]=a[i-1][1]+a[i-1][n-1];
}
else if(j==n-1) //最后一个同学
{
a[i][j]=a[i-1][0]+a[i-1][n-2];
}
else //中间的同学
{
a[i][j]=a[i-1][j-1]+a[i-1][j+1];
}
}
}

System.out.println(a[m-1][0]); //小蛮
}
}