蓝桥杯算法训练VIP-传球游戏 （Java代码）

解题思路:

     本题有两种解法：递归法和动态规划法, 但思路上一致：

     第m次到达第i号人的情况 = 第(m-1)次到达第(i+n+1)%n号人的情况 + 第(m-1)次到达第(i+n-1)%n号人的情况  

     代码中提供了两种解法的代码，递归法超时，使用动态规划用空间换时间，可以AC本题。

注意事项:





参考代码:

import java.util.Scanner;

public class C1610 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {
			int rs = F(sc.nextInt(), sc.nextInt());
			System.out.println(rs);
		}
		sc.close();
	}
	
	//递归解法(超时)：n个人第m次传球时球所在的位置
	/*private static int F(int n, int m, int i){
		if(m == 1){
			if(i == 1 || i == n-1)
				return 1;
			else
				return 0;
		}else{
			return F(n, m-1, (i+n+1)%n) + F(n, m-1, (i+n-1)%n);
		}
	}*/
	
	//动态规划解法: a[i][j]表示第i(0~m-1)次传球传到第j(0~n-1)个人手里的可能性
	private static int F(int n, int m){
		int[][] a = new int[m][n];
		
		//第一行: 只传一次的情况, 只有索引为1和n-1位置才能接到球
		for(int j = 0; j < n; j++){
			if(j == 1 || j == n-1)
				a[0][j] = 1;
		}
		
		for(int i = 1; i < m; i++){
			for(int j = 0; j < n; j++){
				a[i][j] = a[i-1][(j+n+1)%n] + a[i-1][(j+n-1)%n];
			}
		}
		
		return a[m-1][0];
	}
	
}