【算法学习笔记】27.动态规划解题报告 SJTU_OJ 1254 传手绢

浏览数：26 / 时间：2015年06月08日

Description

活动的时候，老师经常带着同学们一起做游戏。这次，老师带着同学们一起传手绢。

游戏规则是这样的：n个同学站成一个圆圈，其中的一个同学手里拿着手绢，当老师吹哨子时开始传，每个同学可以把手绢传给自己左右的两个同学中的一个（左右任意），当老师在此吹哨子时，游戏停止，此时，拿着手绢的那个同学要给大家表演一个节目。

abc提出一个有趣的问题：有多少种不同的传手绢方法可以使得从abc手里开始传的手绢，传了m次以后，又回到abc手里。两种传手绢方法被视作不同的方法，当且仅当这两种方法中，接到球的同学按接手绢顺序组成的序列是不同的。比如有三个同学1号、2号、3号，并假设abc为1号，手绢传了3次回到abc手里的方式有1->2->3->1和1->3->2->1，共2种。

Input Format

共一行，有两个用空格隔开的整数n，m（3<=n<=30，1<=m<=30）。

Output Foramt

共一行，有一个整数，表示符合题意的方法数。

Sample Input

3 3

Sample Output

Hint

40%的数据满足：3<=n<=30，1<=m<=20 100%的数据满足：3<=n<=30，1<=m<=30

此问题很容易让人联想到邻接矩阵乘法含义。wiki了一下，这类问题叫做”传球问题“

证明在这里矩阵乘法确实好理解但是实际应用还是稍微复杂，

这里先用一个递归方案来把这个问题进行解析。

注意到一个人传球，只能传左一位和右一位，根据这个突破点就可以写成递归函数。

/*分治法
返回 一共n个人 还剩m次传球机会 最终传到第k个人手里的路线数
k是当前拿球的人的编号 1号是最开始拿球的人
*/
int passGame(int k,int n, int m){
    if(m==0)
        //若还剩0次传球机会 整好到了原处 那就返回1 表示原来的路线是对的 否则是0
        return (k==1) ? 1 : 0;
    m--;//开始传球了 所以要减少一次传球机会
    //向+1传的话
    int ans1 = passGame((k==n ? 1 : k+1 ),n,m);
    //向-1传的话
    int ans2 = passGame((k==1 ? n : k-1 ),n,m);

    return ans1+ans2;

}

分治法

然后调用passGame(1,n,m)即可

会超时，这种分治法的解决方案是从顶至底的。它会有很多重复的计算，所以我们就会想到和分治法路线相反的动态规划。

动态规划的一个核心思想就是将重复子问题提前计算，从而减少计算量。这也就意味着它必须从底向上计算。

在这个背景下，我们可能直觉想到的是设置一个dp[n][m] 其中d[n][m]表示n个人传m次回到原点的方案数，

然后想办法建立起 d[n][m]和d[n][m-1]的关系或者和 d[n-1][m]的关系或者和d[n-1][m-1]的关系，从而实现把这个问题分成若干个子问题来进行DP。

但是发现找到他们之间的关系，非常困难。

我们试着换一个思路，由分治法的思维，我们知道了一个事情就是还剩s次传球机会时，球传到第k个人手里的路线数 = 还剩s-1次传球机会时，球传到第k+1个人手里的路线数 + 还剩s-1次传球机会，求传到第k-1个人手里的路线数

PS s-1的原因是最后还要耗费一次传球机会来把球传到k手里 k+1 k-1 只是简单的表示k的左右

那么我们就可以考虑构造一个dp[][]来存储还剩m次机会传到第k个人手里的路线数目这个dp方案就是把分治法给颠倒了而已思路是完全一模一样的

//动态规划算法
int dp[35][35]={0};

/*dp[i][j]表示 传i次球 传到第j个人的路线的个数
起始点和终止点都是为1号人
*/
int dp_game(int n,int m){
    dp[0][1]=1;//传0次 传到1号人手中 路线只有一个
    //开始找状态转移方程 
    /*其实想法很简单 就是想d[i][j]是从哪些状态过来的 
        d[i][j]应该是d[i-1][j-1]和d[i-1][j+1]来的 因为j只能收到j-1和j+1的球
        而每次传球恰好i+1
    传0次球 只有1号人才能接到球 其他人都是0 不用算

    */
    for (int i = 1; i <= m; ++i){
        for (int j=1; j <= n; ++j){
            dp[i][j] = dp[i-1][j==1 ? n: j-1 ] + dp[i-1][j==n? 1:j+1];
        }
    }
    return dp[m][1];
}