Q34 左右に行ったり来たり

JavaScriptのソース

Solve( 6);
Solve(12);

function Solve(pN)
{
    const UB = pN - 2;

    //場合の数[左のマス数][右のマス数]なDP表
    var PrevDP = DeriveDPArr(UB);
    PrevDP[0][pN - 2] = 1;

    for(var I = 1 ; I <= pN - 2 ; I++){
        var CurrDP = DeriveDPArr(UB);

        for(var J = 0 ; J <= UB ; J++){
            for(var K = 0 ; K <= UB ; K++){
                if(PrevDP[J][K] == 0) continue;

                //右に移動する場合
                if(I%2 == 1){
                    for(var L = 0 ; L <= K - 1 ; L++){
                        var NewJ = J + L;
                        var NewK = K - 1 - L;
                        CurrDP[NewJ][NewK] += PrevDP[J][K];
                    }
                }

                //左に移動する場合
                else{
                    for(var L = 0 ; L <= J - 1 ; L++){
                        var NewJ = J - 1 - L;
                        var NewK = K + L;
                        CurrDP[NewJ][NewK] += PrevDP[J][K];
                    }
                }
            }
        }
        PrevDP = CurrDP;
    }
    document.write('N=' , pN , 'だと' , PrevDP[0][0] , '通り<br>');
}

function DeriveDPArr(pUB)
{
    var DPArr = new Array(pUB + 1);
    for(var I = 0 ; I <= pUB ; I++){
        DPArr[I] = new Array(pUB + 1);
        DPArr[I].fill(0);
    }
    return DPArr;
}

実行結果

N=6だと5通り
N=12だと50521通り

解説

動的計画法で解いてます。