python-传球游戏

解题思路:

开始我以为是一个递归的题目，写出程序之后数据较大的话时间就会超时。后来参考了别人的答案之后发现是用动态规划的算法。

一楼楼主写的题解很好，大家可以去看看。

这里也简单写以下思路吧

首先建立一个（m+1）*n的数组，暂且起名叫stu吧，m是传球次数（开始是0次），n是学生个数。初始化数组中的值全为零。stu[i][j]的值代表的含义是第i次传球后第j个同学拿到球的可能次数。传球0次的时候球在小蛮手中，因此初始化stu[0][1] = 1。接下来我们可以知道，

第i次传球时某个同学可能会从他左边的同学手中接过球，也有可能会从他右边的同学手中接过球。因此我们可以得到公式

stu[i][j] = stu[i-1][j-1]+stu[i-1][j+1]

我们也要考虑特殊的情况

①第i次传球后球在1号同学手中，此时

stu[i][j] = stu[i-1][n]+stu[i-1][j+1]

①第i次传球后球在n号同学手中，此时

stu[i][j] = stu[i-1][j-1]+stu[i-1][1]

接下来大家看代码应该就能理解了。

注意事项:

参考代码:

def f(n,m):  
    stu = [[0 for j in range(n+1)] for i in range(m+1)]  
    stu[0][1] = 1  
  
    for i in range(1,m+1):  
        for j in range(1,n+1):  
            if j == 1:  
                stu[i][j] = stu[i-1][n]+stu[i-1][j+1]  
            elif j == n:  
                stu[i][j] = stu[i-1][j-1]+stu[i-1][1]  
            else:  
                stu[i][j] = stu[i-1][j-1]+stu[i-1][j+1]  
      
    print(stu[m][1])  
      
  
  
if __name__ == '__main__':  
    n,m = map(int,input().strip().split())  
    f(n,m)