Q27 大家族でチョコレートを分けるには

JavaScriptのソース

Solve( 3, 4, 3); //         17
Solve(20,20,10); //16420955656

function Solve(pYoko,pTate,pNinzuu)
{
    //場合の数[横幅][縦幅]なDP表
    var PrevDP = new Object();
    for(var X = 1 ; X <= pYoko ; X++){
        PrevDP[X] = new Object();
        for(var Y = 1 ; Y <= pTate ; Y++){
            PrevDP[X][Y] = 0;
        }
    }
    PrevDP[pYoko][pTate] = 1;

    for(var I = 1 ; I <= pNinzuu - 1 ; I++){
        var CurrDP = new Object();
        for(var X = 1 ; X <= pYoko ; X++){
            CurrDP[X] = new Object();
            for(var Y = 1 ; Y <= pTate ; Y++){
                CurrDP[X][Y] = 0;
            }
        }

        for(var X = 1 ; X <= pYoko ; X++){
            for(var Y = 1 ; Y <= pTate ; Y++){
                if(PrevDP[X][Y] == 0) continue;
                for(var NewX = 1 ; NewX <= X - 1 ; NewX++){
                    CurrDP[NewX][Y] += PrevDP[X][Y];
                }
                for(var NewY = 1 ; NewY <= Y - 1 ; NewY++){
                    CurrDP[X][NewY] += PrevDP[X][Y];
                }
            }
        }
        PrevDP = CurrDP;
    }

    var Answer = 0;
    for(var X = 1 ; X <= pYoko ; X++){
        for(var Y = 1 ; Y <= pTate ; Y++){
            Answer += PrevDP[X][Y];
        }
    }
    document.write("横幅=", pYoko , ",縦幅=", pTate);
    document.write(",人数=" , pNinzuu , "では、" , Answer , "通り" , "<br>");
}

実行結果

横幅=3,縦幅=4,人数=3では、16通り
横幅=20,縦幅=20,人数=10では、16420955656通り

解説

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