算法學習之路|蒜頭君的新遊戲1

工作空閑之餘，蒜頭君經常帶着同僚們做遊戲，最近蒜頭君發明了一個好玩的新遊戲：nn 位同僚圍成一個圈，同僚 A 手裡拿着一個兔妮妮的娃娃。蒜頭君喊遊戲開始，每位手裡拿着娃娃的同僚可以選擇将娃娃傳給左邊或者右邊的同學，當蒜頭君喊遊戲結束時，停止傳娃娃。此時手裡拿着娃娃的同僚即是敗者。

玩了幾輪之後，蒜頭君想到一a個問題：有多少種不同的方法，使得從同僚 A 開始傳娃娃，傳了 mm 次之後又回到了同僚 A 手裡。兩種方法，如果接娃娃的同僚不同，或者接娃娃的順序不同均視為不同的方法。例如 1−>2−>3−>11−>2−>3−>1 和 1−>3−>2−>11−>3−>2−>1 是兩種不同的方法。

輸入格式

輸入一行，輸入兩個整數 n,m(3≤n≤30,1≤m≤30)n,m(3≤n≤30,1≤m≤30)，表示一共有 nn 位同僚一起遊戲，一共傳 mm 次娃娃。

輸出格式

輸出一行，輸出一個整數，表示一共有多少種不同的傳娃娃方法。

樣例輸入

3 3

樣例輸出

2

本體的難點是分出階段，找出決策，列出狀态轉移方程。

我們把dpi看做所剩i步，到達同僚j所有種情況數。

看例題：我們編号3位同僚0~2，如果求0~0的所有情況，那麼就要知道在還剩下1步的情況下，

到達1，2的所有情況，即dp0=dp1+dp1;

是以，我們得出狀态轉移方程dpi=dpi+1+dpi-1.//思路對的，不考慮環路

(因為是環路，是以應該改為dpi=dpi+1+dpi+1;)

最後，我們列出特殊情況：

即當所剩步數是m時，隻有dp0=1

(自己到自己肯定不需要走嘛，其他dp0=0,因為0号到其他肯定要走路,不存在0~其他 無需走路的情況)