状态表示

这个题目是个环形的dp。f[i][j]表示走了i步，当球恰好传给j同学的方案数。

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.StringTokenizer;

public class Main {
    static int n,m;
    static int f[][]=new int[31][31];
    public static void main(String[] args)throws Exception {

       // System.setIn(new FileInputStream("E:\\data\\p1057.txt"));
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer(br.readLine());
       n= Integer.parseInt(st.nextToken());
       m= Integer.parseInt(st.nextToken());
       f[0][1]=1;
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(j==1){//表示在第一个同学的手里，他手里的方案数有两个可能，从最后一个过来，或者是从第二个同学的手里过来
                    f[i][j]=f[i-1][n]+f[i-1][2];
                }else if(j==n){//表示在最后一个同学的手里，他手里的方案数则表示第一个同学过来或者倒数第二个同学过来
                    f[i][j]=f[i-1][n-1]+f[i-1][1];
                }else{
                    f[i][j]=f[i-1][j-1]+f[i-1][j+1];
                }
            }
        }
        System.out.println(f[m][1]);
    }
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla