大神的世界

利用 DP (dynamic programming)

DP 簡單來說，就是考慮上一步 （或 下一步）

以這題來說，是考慮下一步

假設 step[ i ][ j ][ k ] 代表 有 i 人 ，球在 j 手上，傳 k 次後，能回到 1 號手上的方法數

則它的方法數就等於 step[ i ][ j-1 ][ k-1 ] + step[ i ][ j+1 ][ k-1 ]

因為 j 號要麼傳給左邊 （ j-1 ) 要麼傳給右邊（ j+1 ) ，且剩餘次數為 k-1

因此我們得到一條關係式

step[ i ][ j ][ k ] =  step[ i ][ j-1 ][ k-1 ] + step[ i ][ j+1 ][ k-1 ]

另外，跟遞迴一樣，DP 也要設 boundary condition （凡事要有個頭）

因為 k 從 1 開始，所以初始條件為 k = 0

即 step[ i ][ j ][ 0 ]

很明顯當 j = 1 時，其值為 1 否則為 0

#include <iostream>

using namespace std;

int step[31][31][31];

void setTable()
{
    int i, j, k;

    for(i = 3; i<=30; i++)
        step[i][1][0] = 1;

    for(i = 3; i<=30; i++)
        for(k = 1 ; k<=30; k++)
            for(j = 1; j<= i; j++)
                if(j == 1)
                    step[i][j][k] = step[i][i][k-1] + step[i][j+1][k-1];
                else if(j == i)
                    step[i][j][k] = step[i][j-1][k-1] + step[i][1][k-1];
                else
                    step[i][j][k] = step[i][j-1][k-1] + step[i][j+1][k-1];
}

int main()
{
    int people;
    int pass;

    setTable();
    while(cin >> people >> pass)
        cout << step[people][1][pass] << endl;

    return 0;
}