击鼓传花

题目

学校联欢晚会的时候，为了使每一个同学都能参与进来，主持人常常会带着同学们玩击鼓传花的游戏。游戏规则是这样的：n个同学坐着围成一个圆圈，指定一个同学手里拿着一束花，主持人在旁边背对着大家开始击鼓，鼓声开始之后拿着花的同学开始传花，每个同学都可以把花传给自己左右的两个同学中的一个（左右任意），当主持人停止击鼓时，传花停止，此时，正拿着花没传出去的那个同学就要给大家表演一个节目。

输入

step：传的次数
num：人数（同学编号从1-num）

输出

result: 从1号同学开始传递，重新回到1号同学的路径个数

状态转移方程

每一个同学编号从1-num；
保存状态的二维数组：dp[step+1][num+1]
初始状态：

dp[0][1] = 1 //一号同学初始状态
dp[1][2] = 1 //从1号同学经过一步到2号同学
dp[1][num] = 1 //从1号同学经过一步到num号同学

• 如果从编号为1的同学开始，则状态转移：dp[i][1] = dp[i-1][n]+dp[i-1][2]
• 如果从编号为n的同学开始，则状态转移：dp[i][n] = dp[i-1][n-1]+dp[i-1][1]
• 其余情况，状态转移：dp[i][j] = dp[i-1][j-1]+dp[i-1][j+1]

code

public static int solution(int step,int num){
        int[][] dp = new int[step+1][num+1];

        dp[0][1] = 1;
        dp[1][2] = 1;
        dp[1][num] = 1;

        for (int i=1;i<=step;i++){
            for (int j=1;j<=num;j++){

                if (j==1)
                    dp[i][j] = dp[i-1][num]+dp[i-1][2];
                else if (j==num)
                    dp[i][j] = dp[i-1][num-1]+dp[i-1][1];
                else
                    dp[i][j] = dp[i-1][j-1]+dp[i-1][j+1];

            }
        }
        return dp[step][1];
    }