Q37 ダイヤルロックを解除せよ！

JavaScriptのソース

Solve( 3, 6);
Solve(10,50);

function Solve(pKetasuu , pMoveCnt)
{
    const UB = pMoveCnt;

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

    for(var I = 1 ; I <= pKetasuu ; 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 <= 9 ; K++){
                var NewJ = J + K;
                if(UB < K) break;
                CurrDP[NewJ] += PrevDP[J];
            }
        }
        //document.write(JSON.stringify(PrevDP));
        PrevDP = CurrDP;
    }
    document.write('鍵の桁数=' , pKetasuu , ',動かす目盛=' , pMoveCnt , 'だと、' , PrevDP[UB] , '通り<br>');
}

実行結果

鍵の桁数=3,動かす目盛=6だと、10通り
鍵の桁数=10,動かす目盛=50だと、167729959通り

解説

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