Q28 パターゴルフのコース設計

JavaScriptのソース

Solve( 3,12);
Solve(18,72);

function Solve(pHall,pDasuu)
{
    const UB = pDasuu;

    //場合の数[合計打数]なDP表
    var PrevDP = new Array(UB + 1).fill(0);
    PrevDP[0] = 1;

    for(var I = 1 ; I <= pHall ; I++){
        var CurrDP = new Array(UB + 1).fill(0);
        for(var J = 0 ; J <= UB ; J++){
            if(PrevDP[J] == 0) continue;
            for(var K = 1 ; K <= 5 ; K++){
                var NewJ = J + K;
                if(UB < NewJ) break;
                CurrDP[NewJ] += PrevDP[J];
            }
        }
        PrevDP = CurrDP;
    }
    document.write(pHall , 'ホールで合計打数が' , pDasuu , 'だと' ,  PrevDP[UB] , '通り<br>');
}

実行結果

3ホールで合計打数が12だと10通り
18ホールで合計打数が72だと2546441085通り

解説

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