概要

アルゴリズムの学習記録を投稿します。
今回は蟻本p66の動的計画法の分割数についてです。

問題

p66

n個の互いに区別できない品物を、m個以下に分割する方法の総数を求め、Mで割った余りを答えなさい。

入力
n = 4
m = 3
M = 10000

出力
4

コード部分

/**
 * 　分割数を計算する
 *
 * @param {Number} n - 品物の数
 * @param {Array} m -  分割する数
 * @param {Number} M  - 割った数
 * @return {Number}  -価値の総和
 */
const calDivisionNumber = (n,m,M) =>{
    let dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
    // let dp = new Array(number1 + 1).fill(0).map(() => new Array(number2 + 1).fill(0));

    let loopCount = 0;
    console.log(`ループ数|i|j|条件|resの計算式|resの値`);
    console.log(`--|--|-----|----|-----|---`);
    dp[0][0] = 1;
    for(let i = 1;i <= m; i++){
        for(let j = 0; j <= n;j++){
            if(j - i >= 0){
            dp[i][j] = (dp[i-1][j] + dp[i][j-i]) % M;
            loopCount++;
            console.log(`${loopCount}|${i}|${j}|j - i >0 </br> ${j}-${i} >0|dp[i-1][j] + dp[i][j-i] </br> dp[${i} -1]\\[${j}](=${dp[i-1][j]}) +dp[${i}]\\[${j}-${i}](=${dp[i][j-i]})|dp[${i}][${j}]</br>=${dp[i][j]} `)
        }
        else
        {
            dp[i][j] = dp[i - 1][j];
            loopCount++;
            console.log(`${loopCount}|${i}|${j}|j - i < 0 </br> ${j}-${i} < 0|dp[i-1][j] </br>dp[${i}-1][${j}] |dp[${i}][${j}]</br>=${dp[i][j]}`)
        }
        }
    }
    console.log(dp);
    return dp[m][n];
}

// 結果値は4
calDivisionNumber(4,3,10000)

python tutor

コードを実際に動かせるwebサイト
ステップ実行かつステップ事の変数を確認できる特徴があります。
リンク

その他情報

感想

漸化式を決めるまでが難しいと感じました。
漸化式が決まってからの実装は易です。

依存関係グラフ

依存関係グラフは変数の結びつきを一目でわかりやすくするための図です。
変数の流れを確認しやすくすることでワーキングメモリの負担を減らすことができます。
作成方法はコード上の変数に丸付けて線を繋げています。

状態遷移図

計算内容を明示する表。
ステップごとの変数の値を各列に表示します。
複雑な計算を行うコードを理解するのに役立つ表です。

ループ数1のとき　4
ループ数8のとき　2+2 or 1+3
ループ数10のとき　2+2 or 1+3
ループ数15のとき　1+1+2

ループ数	i	j	条件	resの計算式	resの値
1	1	0	j - i < 0 0-1 < 0	dp[i-1][j] dp[1-1][0]	dp[1][0]=1
2	1	1	j - i >0 1-1 >0	dp[i-1][j] + dp[i][j-i] dp[1 -1][1](=0) +dp[1][1-1](=1)	dp[1][1]=1
3	1	2	j - i >0 2-1 >0	dp[i-1][j] + dp[i][j-i] dp[1 -1][2](=0) +dp[1][2-1](=1)	dp[1][2]=1
4	1	3	j - i >0 3-1 >0	dp[i-1][j] + dp[i][j-i] dp[1 -1][3](=0) +dp[1][3-1](=1)	dp[1][3]=1
5	1	4	j - i >0 4-1 >0	dp[i-1][j] + dp[i][j-i] dp[1 -1][4](=0) +dp[1][4-1](=1)	dp[1][4]=1
6	2	0	j - i < 0 0-2 < 0	dp[i-1][j] dp[2-1][0]	dp[2][0]=1
7	2	1	j - i < 0 1-2 < 0	dp[i-1][j] dp[2-1][1]	dp[2][1]=1
8	2	2	j - i >0 2-2 >0	dp[i-1][j] + dp[i][j-i] dp[2 -1][2](=1) +dp[2][2-2](=1)	dp[2][2]=2
9	2	3	j - i >0 3-2 >0	dp[i-1][j] + dp[i][j-i] dp[2 -1][3](=1) +dp[2][3-2](=1)	dp[2][3]=2
10	2	4	j - i >0 4-2 >0	dp[i-1][j] + dp[i][j-i] dp[2 -1][4](=1) +dp[2][4-2](=2)	dp[2][4]=3
11	3	0	j - i < 0 0-3 < 0	dp[i-1][j] dp[3-1][0]	dp[3][0]=1
12	3	1	j - i < 0 1-3 < 0	dp[i-1][j] dp[3-1][1]	dp[3][1]=1
13	3	2	j - i < 0 2-3 < 0	dp[i-1][j] dp[3-1][2]	dp[3][2]=2
14	3	3	j - i >0 3-3 >0	dp[i-1][j] + dp[i][j-i] dp[3 -1][3](=2) +dp[3][3-3](=1)	dp[3][3]=3
15	3	4	j - i >0 4-3 >0	dp[i-1][j] + dp[i][j-i] dp[3 -1][4](=3) +dp[3][4-3](=1)	dp[3][4]=4

[
[ 1, 0, 0, 0, 0 ],
[ 1, 1, 1, 1, 1 ],
[ 1, 1, 2, 2, 3 ],
[ 1, 1, 2, 3, 4 ]
]

他の例　n=2 m=2 結果値　２個

ループ数	i	j	条件	resの計算式	resの値
1	1	0	j - i < 0 0-1 < 0	dp[i-1][j] dp[1-1][0]	dp[1][0]=1
2	1	1	j - i >0 1-1 >0	dp[i-1][j] + dp[i][j-i] dp[1 -1][1](=0) +dp[1][1-1](=1)	dp[1][1]=1
3	1	2	j - i >0 2-1 >0	dp[i-1][j] + dp[i][j-i] dp[1 -1][2](=0) +dp[1][2-1](=1)	dp[1][2]=1
4	2	0	j - i < 0 0-2 < 0	dp[i-1][j] dp[2-1][0]	dp[2][0]=1
5	2	1	j - i < 0 1-2 < 0	dp[i-1][j] dp[2-1][1]	dp[2][1]=1
6	2	2	j - i >0 2-2 >0	dp[i-1][j] + dp[i][j-i] dp[2 -1][2](=1) +dp[2][2-2](=1)	dp[2][2]=2

[
[ 1, 0, 0 ],
[ 1, 1, 1 ],
[ 1, 1, 2 ]
]

dpの動き

他の例　n=3 m=3 結果値　3個

ループ数	i	j	条件	resの計算式	resの値
1	1	0	j - i < 0 0-1 < 0	dp[i-1][j] dp[1-1][0]	dp[1][0]=1
2	1	1	j - i >0 1-1 >0	dp[i-1][j] + dp[i][j-i] dp[1 -1][1](=0) +dp[1][1-1](=1)	dp[1][1]=1
3	1	2	j - i >0 2-1 >0	dp[i-1][j] + dp[i][j-i] dp[1 -1][2](=0) +dp[1][2-1](=1)	dp[1][2]=1
4	1	3	j - i >0 3-1 >0	dp[i-1][j] + dp[i][j-i] dp[1 -1][3](=0) +dp[1][3-1](=1)	dp[1][3]=1
5	2	0	j - i < 0 0-2 < 0	dp[i-1][j] dp[2-1][0]	dp[2][0]=1
6	2	1	j - i < 0 1-2 < 0	dp[i-1][j] dp[2-1][1]	dp[2][1]=1
7	2	2	j - i >0 2-2 >0	dp[i-1][j] + dp[i][j-i] dp[2 -1][2](=1) +dp[2][2-2](=1)	dp[2][2]=2
8	2	3	j - i >0 3-2 >0	dp[i-1][j] + dp[i][j-i] dp[2 -1][3](=1) +dp[2][3-2](=1)	dp[2][3]=2
9	3	0	j - i < 0 0-3 < 0	dp[i-1][j] dp[3-1][0]	dp[3][0]=1
10	3	1	j - i < 0 1-3 < 0	dp[i-1][j] dp[3-1][1]	dp[3][1]=1
11	3	2	j - i < 0 2-3 < 0	dp[i-1][j] dp[3-1][2]	dp[3][2]=2
12	3	3	j - i >0 3-3 >0	dp[i-1][j] + dp[i][j-i] dp[3 -1][3](=2) +dp[3][3-3](=1)	dp[3][3]=3

[ [ 1, 0, 0, 0 ],
[ 1, 1, 1, 1 ],
[ 1, 1, 2, 2 ],
[ 1, 1, 2, 3 ] ]

dpの動き

他の例　n=4 m=4 結果値　5個

ループ数	i	j	条件	resの計算式	resの値
1	1	0	j - i < 0 0-1 < 0	dp[i-1][j] dp[1-1][0]	dp[1][0]=1
2	1	1	j - i >0 1-1 >0	dp[i-1][j] + dp[i][j-i] dp[1 -1][1](=0) +dp[1][1-1](=1)	dp[1][1]=1
3	1	2	j - i >0 2-1 >0	dp[i-1][j] + dp[i][j-i] dp[1 -1][2](=0) +dp[1][2-1](=1)	dp[1][2]=1
4	1	3	j - i >0 3-1 >0	dp[i-1][j] + dp[i][j-i] dp[1 -1][3](=0) +dp[1][3-1](=1)	dp[1][3]=1
5	1	4	j - i >0 4-1 >0	dp[i-1][j] + dp[i][j-i] dp[1 -1][4](=0) +dp[1][4-1](=1)	dp[1][4]=1
6	2	0	j - i < 0 0-2 < 0	dp[i-1][j] dp[2-1][0]	dp[2][0]=1
7	2	1	j - i < 0 1-2 < 0	dp[i-1][j] dp[2-1][1]	dp[2][1]=1
8	2	2	j - i >0 2-2 >0	dp[i-1][j] + dp[i][j-i] dp[2 -1][2](=1) +dp[2][2-2](=1)	dp[2][2]=2
9	2	3	j - i >0 3-2 >0	dp[i-1][j] + dp[i][j-i] dp[2 -1][3](=1) +dp[2][3-2](=1)	dp[2][3]=2
10	2	4	j - i >0 4-2 >0	dp[i-1][j] + dp[i][j-i] dp[2 -1][4](=1) +dp[2][4-2](=2)	dp[2][4]=3
11	3	0	j - i < 0 0-3 < 0	dp[i-1][j] dp[3-1][0]	dp[3][0]=1
12	3	1	j - i < 0 1-3 < 0	dp[i-1][j] dp[3-1][1]	dp[3][1]=1
13	3	2	j - i < 0 2-3 < 0	dp[i-1][j] dp[3-1][2]	dp[3][2]=2
14	3	3	j - i >0 3-3 >0	dp[i-1][j] + dp[i][j-i] dp[3 -1][3](=2) +dp[3][3-3](=1)	dp[3][3]=3
15	3	4	j - i >0 4-3 >0	dp[i-1][j] + dp[i][j-i] dp[3 -1][4](=3) +dp[3][4-3](=1)	dp[3][4]=4
16	4	0	j - i < 0 0-4 < 0	dp[i-1][j] dp[4-1][0]	dp[4][0]=1
17	4	1	j - i < 0 1-4 < 0	dp[i-1][j] dp[4-1][1]	dp[4][1]=1
18	4	2	j - i < 0 2-4 < 0	dp[i-1][j] dp[4-1][2]	dp[4][2]=2
19	4	3	j - i < 0 3-4 < 0	dp[i-1][j] dp[4-1][3]	dp[4][3]=3
20	4	4	j - i >0 4-4 >0	dp[i-1][j] + dp[i][j-i] dp[4 -1][4](=4) +dp[4][4-4](=1)	dp[4][4]=5

[
[ 1, 0, 0, 0, 0 ],
[ 1, 1, 1, 1, 1 ],
[ 1, 1, 2, 2, 3 ],
[ 1, 1, 2, 3, 4 ],
[ 1, 1, 2, 3, 5 ]
]

dpの動き

面倒なのでパスします！

参考資料

プログラミングコンテストチャレンジブック [第2版]　マイナビ　p66

プログラマー脳　秀和システム
p73 python tutor
p71 状態遷移表　
p69 依存関係グラフ

githubコミット部分