平凡


私信TA

用户名:uq_30153938431

访问量:7858

签 名:

等  级
排  名 949
经  验 3251
参赛次数 0
文章发表 16
年  龄 20
在职情况 学生
学  校 广西建设职业技术学院
专  业 网络技术

  自我简介:

已经升本了。

       

/*
     *                 
     *    最优解子结构:根据题目描述,我们知道球可以左右传,所有人围成一个园,这就代表了球在任何一个人手上都能传出去。
     *                 然后问题是要求我们计算出球传了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]);
    }
    
    
    
    //嗯.....,思路仅供参考,我做了之后看了一下其他人的题解....,我发现状态转移方程都一样,但是是我自己按照算法导论的分析方法去分析的。而且分析得还不够好。
    //先这样后面完善了再重新上传。大家等我啊,我有时间就给出详细的思路,现在要去做饭了...


 

0.0分

5 人评分

  评论区