擊鼓傳花
題目
學(xué)校聯(lián)歡晚會的時候粪摘，為了使每一個同學(xué)都能參與進(jìn)來伤锚，主持人常常會帶著同學(xué)們玩擊鼓傳花的游戲秀存。游戲規(guī)則是這樣的：n個同學(xué)坐著圍成一個圓圈性誉，指定一個同學(xué)手里拿著一束花，主持人在旁邊背對著大家開始擊鼓杨蛋，鼓聲開始之后拿著花的同學(xué)開始傳花兜材，每個同學(xué)都可以把花傳給自己左右的兩個同學(xué)中的一個（左右任意）理澎，當(dāng)主持人停止擊鼓時，傳花停止曙寡，此時糠爬，正拿著花沒傳出去的那個同學(xué)就要給大家表演一個節(jié)目。
輸入
step：傳的次數(shù)
num：人數(shù)（同學(xué)編號從1-num）
輸出
result: 從1號同學(xué)開始傳遞举庶，重新回到1號同學(xué)的路徑個數(shù)
狀態(tài)轉(zhuǎn)移方程
每一個同學(xué)編號從1-num执隧；
保存狀態(tài)的二維數(shù)組：dp[step+1][num+1]
初始狀態(tài)：
dp[0][1] = 1 //一號同學(xué)初始狀態(tài)
dp[1][2] = 1 //從1號同學(xué)經(jīng)過一步到2號同學(xué)
dp[1][num] = 1 //從1號同學(xué)經(jīng)過一步到num號同學(xué)
- 如果從編號為1的同學(xué)開始，則狀態(tài)轉(zhuǎn)移：dp[i][1] = dp[i-1][n]+dp[i-1][2]
- 如果從編號為n的同學(xué)開始户侥，則狀態(tài)轉(zhuǎn)移：dp[i][n] = dp[i-1][n-1]+dp[i-1][1]
- 其余情況镀琉，狀態(tài)轉(zhuǎn)移：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];
}
