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

/*
     *                 
     *    最优解子结构：根据题目描述，我们知道球可以左右传，所有人围成一个园，这就代表了球在任何一个人手上都能传出去。
     *                 然后问题是要求我们计算出球传了m次，有多少条路径可以回到1号手中。这样，我们随便拿出一个问题来分析。
     *                     比如：三个人，传三次。方便研究，我们给人表示记号1,2,3
     *                        
     *                开始的时候球在第一个人手中。()代表之前的终点，[]代表同一个起点的路径
     *                第一次：球可能传给2|3，这个时候的路径是[1-->2|1-->3]
     *                第二次：球可能传给3|1，这个时候的路径是[(1)-->2-->1|(1)-->2-->3][(1)-->3-->2|(1)-->3-->1] 
     *                第三次：球现在在的位置是3|1都有俩种路径到达。
     *                        [(1)-->(2)-->1-->2|(1)-->(2)-->1-->3|(1)-->(3)-->1-->2|(1)-->(3)-->1-->3]
     *                        [(1)-->(2)-->3-->2|(1)-->(2)-->3-->1]
     *                        [(1)-->(3)-->2-->3|(1)-->(3)-->2-->1]
     *                        看一下终点是到达1的就两个(1)-->(2)-->3-->1|(1)-->(3)-->2-->1
     *                看一下我们是怎么研究这个问题的：
     *                    第一：确定号数，就是哪位同学代表几号。
     *                    第二：确定球传出去的次数。
     *                    第三：最后统计到达符合自己目的的路径。本问题两个
     *
     *            ---然后我们发现这些次数与次数之间有一种关系，就是第三次的起点是第二次的终点。
     *                  第二次的起点也是第一次的终点
     *            ---我们来假设：我们是不是只需要第几位同学第几次，球经过他这个位置的次数就可以知道路径的总数了？
     *                  就可以知道下一次球在第几次在哪个同学，可能出现的次数了。
     *               -- 我们来证明一下，为了方便证明我们把每一位同学标记为A[i,j],i代表号数、j代表球传的次数（下面简称次数）
     *                    A[i,j]代表球出现的次数
     *               -- 首先，球是可以左右传，一堆人围成一个圆圈。当我是第一次从1传的时候，可以传两个位置。
     *                    第二次的时候就是2|n对下一个进行传球，每一个位置是不是又可以传两个位置，一共有四种传法....
     *                  但是这些起点是不是都依赖第一次的终点，第一次有多少个终点就以*2的方式继续往下传，不管到没到1
     *                  路径还是存在的。啊啊啊，不懂怎么证明，凭想象...
     *                
     *    递归解决问题：    按照上面的我们在计算A[i,j]的时候，就需要看上一次它相邻两边球可能传的次数，然后相加就得到当前
     *                  同学在第j次时球可能传到他手上的次数了。
     *                  就得到方程：A[i][j] = A[i-1][j-1] + A[i+1][j-1]
     *                    但是啊，1可以传给n，n也可以传给1。他们不可能通过1-1就得到n，n-1就得到1的。
     *                所以还是要特殊考虑的：A[1][j] = A[2][j-1] + A[n][j-1]
     *                                     A[n][j] = A[1][j-1] + A[n-1][j-1]
     *
     *    最后：我们只要根据球到达哪个终点，第几次到达就可以得到第几次到达这个同学的次数了。
                     比如个是：到达一号同学，第m次到达。所以最后的答案是dp[1][m]
     *                  
     */               

public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int dp[][] = new int[n+1][m+1];
        dp[2][1] = 1;dp[n][1] = 1;//第一次的时候，是1-->2 1-->n
        dp[1][m] = 1;
        for (int i = 2; i <= m; i++) {//次数啊
            for (int j = 1; j <= n; j++) {//号数啊，我自己都做错了...，好无语
                if(j == 1) {
                    dp[1][i] = dp[n][i-1] + dp[2][i-1];
                }else if(j == n ) {
                    dp[j][i] = dp[n-1][i-1] + dp[1][i-1];
                }else {
                    dp[j][i] = dp[j+1][i-1] + dp[j-1][i-1];
                }
            }
        }
        System.out.println(dp[1][m]);
    }
    
    
    
    //嗯.....，思路仅供参考，我做了之后看了一下其他人的题解....，我发现状态转移方程都一样，但是是我自己按照算法导论的分析方法去分析的。而且分析得还不够好。
    //先这样后面完善了再重新上传。大家等我啊，我有时间就给出详细的思路，现在要去做饭了...