JavaScriptで蟻本 動的計画法　分割数

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


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

入力
n = 4
m = 3
M = 10000

出力
4
```


# コード部分
```javascript
/**
 * 　分割数を計算する
 *
 * @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サイト
ステップ実行かつステップ事の変数を確認できる特徴があります。
[リンク](https://pythontutor.com/render.html#code=/**%0A%20*%20%E3%80%80%E5%88%86%E5%89%B2%E6%95%B0%E3%82%92%E8%A8%88%E7%AE%97%E3%81%99%E3%82%8B%0A%20*%0A%20*%20%40param%20%7BNumber%7D%20n%20-%20%E5%93%81%E7%89%A9%E3%81%AE%E6%95%B0%0A%20*%20%40param%20%7BArray%7D%20m%20-%20%20%E5%88%86%E5%89%B2%E3%81%99%E3%82%8B%E6%95%B0%0A%20*%20%40param%20%7BNumber%7D%20M%20%20-%20%E5%89%B2%E3%81%A3%E3%81%9F%E6%95%B0%0A%20*%20%40return%20%7BNumber%7D%20%20-%E4%BE%A1%E5%80%A4%E3%81%AE%E7%B7%8F%E5%92%8C%0A%20*/%0Aconst%20calDivisionNumber%20%3D%20%28n,m,M%29%20%3D%3E%7B%0A%20%20%20%20let%20dp%20%3D%20new%20Array%28m%20%2B%201%29.fill%280%29.map%28%28%29%20%3D%3E%20new%20Array%28n%20%2B%201%29.fill%280%29%29%3B%0A%20%20%20%20//%20let%20dp%20%3D%20new%20Array%28number1%20%2B%201%29.fill%280%29.map%28%28%29%20%3D%3E%20new%20Array%28number2%20%2B%201%29.fill%280%29%29%3B%0A%0A%20%20%20%20let%20loopCount%20%3D%200%3B%0A%20%20%20%20console.log%28%60%E3%83%AB%E3%83%BC%E3%83%97%E6%95%B0%7Ci%7Cj%7C%E6%9D%A1%E4%BB%B6%7Cres%E3%81%AE%E8%A8%88%E7%AE%97%E5%BC%8F%7Cres%E3%81%AE%E5%80%A4%60%29%3B%0A%20%20%20%20console.log%28%60--%7C--%7C-----%7C----%7C-----%7C---%60%29%3B%0A%20%20%20%20dp%5B0%5D%5B0%5D%20%3D%201%3B%0A%20%20%20%20for%28let%20i%20%3D%201%3Bi%20%3C%3D%20m%3B%20i%2B%2B%29%7B%0A%20%20%20%20%20%20%20%20for%28let%20j%20%3D%200%3B%20j%20%3C%3D%20n%3Bj%2B%2B%29%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20if%28j%20-%20i%20%3E%3D%200%29%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20dp%5Bi%5D%5Bj%5D%20%3D%20%28dp%5Bi-1%5D%5Bj%5D%20%2B%20dp%5Bi%5D%5Bj-i%5D%29%20%25%20M%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20loopCount%2B%2B%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20console.log%28%60%24%7BloopCount%7D%7C%24%7Bi%7D%7C%24%7Bj%7D%7Cj%20-%20i%20%3E0%20%3C/br%3E%20%24%7Bj%7D-%24%7Bi%7D%20%3E0%7Cdp%5Bi-1%5D%5Bj%5D%20%2B%20dp%5Bi%5D%5Bj-i%5D%20%3C/br%3E%20dp%5B%24%7Bi%7D%20-1%5D%5C%5C%5B%24%7Bj%7D%5D%28%3D%24%7Bdp%5Bi-1%5D%5Bj%5D%7D%29%20%2Bdp%5B%24%7Bi%7D%5D%5C%5C%5B%24%7Bj%7D-%24%7Bi%7D%5D%28%3D%24%7Bdp%5Bi%5D%5Bj-i%5D%7D%29%7Cdp%5B%24%7Bi%7D%5D%5B%24%7Bj%7D%5D%3C/br%3E%3D%24%7Bdp%5Bi%5D%5Bj%5D%7D%20%60%29%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20else%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20dp%5Bi%5D%5Bj%5D%20%3D%20dp%5Bi%20-%201%5D%5Bj%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20loopCount%2B%2B%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20console.log%28%60%24%7BloopCount%7D%7C%24%7Bi%7D%7C%24%7Bj%7D%7Cj%20-%20i%20%3C%200%20%3C/br%3E%20%24%7Bj%7D-%24%7Bi%7D%20%3C%200%7Cdp%5Bi-1%5D%5Bj%5D%20%3C/br%3Edp%5B%24%7Bi%7D-1%5D%5B%24%7Bj%7D%5D%20%7Cdp%5B%24%7Bi%7D%5D%5B%24%7Bj%7D%5D%3C/br%3E%3D%24%7Bdp%5Bi%5D%5Bj%5D%7D%60%29%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%20%20%20console.log%28dp%29%3B%0A%20%20%20%20return%20dp%5Bm%5D%5Bn%5D%3B%0A%7D%0A%0A//%20%E7%B5%90%E6%9E%9C%E5%80%A4%E3%81%AF4%0AcalDivisionNumber%284,3,10000%29&cumulative=false&curInstr=3&heapPrimitives=nevernest&mode=display&origin=opt-frontend.js&py=js&rawInputLstJSON=%5B%5D&textReferences=false)

# その他情報

## 感想

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

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

![image-4 (1).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2710623/b9e60b25-6250-d969-46bb-e1f1226364b2.png)



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

ループ数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 </br> 0-1 < 0|dp[i-1][j] </br>dp[1-1][0] |dp[1][0]</br>=1
2|1|1|j - i >0 </br> 1-1 >0|dp[i-1][j] + dp[i][j-i] </br> dp[1 -1]\[1](=0) +dp[1]\[1-1](=1)|dp[1][1]</br>=1 
3|1|2|j - i >0 </br> 2-1 >0|dp[i-1][j] + dp[i][j-i] </br> dp[1 -1]\[2](=0) +dp[1]\[2-1](=1)|dp[1][2]</br>=1 
4|1|3|j - i >0 </br> 3-1 >0|dp[i-1][j] + dp[i][j-i] </br> dp[1 -1]\[3](=0) +dp[1]\[3-1](=1)|dp[1][3]</br>=1 
5|1|4|j - i >0 </br> 4-1 >0|dp[i-1][j] + dp[i][j-i] </br> dp[1 -1]\[4](=0) +dp[1]\[4-1](=1)|dp[1][4]</br>=1 
6|2|0|j - i < 0 </br> 0-2 < 0|dp[i-1][j] </br>dp[2-1][0] |dp[2][0]</br>=1
7|2|1|j - i < 0 </br> 1-2 < 0|dp[i-1][j] </br>dp[2-1][1] |dp[2][1]</br>=1
8|2|2|j - i >0 </br> 2-2 >0|dp[i-1][j] + dp[i][j-i] </br> dp[2 -1]\[2](=1) +dp[2]\[2-2](=1)|dp[2][2]</br>=2 
9|2|3|j - i >0 </br> 3-2 >0|dp[i-1][j] + dp[i][j-i] </br> dp[2 -1]\[3](=1) +dp[2]\[3-2](=1)|dp[2][3]</br>=2 
10|2|4|j - i >0 </br> 4-2 >0|dp[i-1][j] + dp[i][j-i] </br> dp[2 -1]\[4](=1) +dp[2]\[4-2](=2)|dp[2][4]</br>=3 
11|3|0|j - i < 0 </br> 0-3 < 0|dp[i-1][j] </br>dp[3-1][0] |dp[3][0]</br>=1
12|3|1|j - i < 0 </br> 1-3 < 0|dp[i-1][j] </br>dp[3-1][1] |dp[3][1]</br>=1
13|3|2|j - i < 0 </br> 2-3 < 0|dp[i-1][j] </br>dp[3-1][2] |dp[3][2]</br>=2
14|3|3|j - i >0 </br> 3-3 >0|dp[i-1][j] + dp[i][j-i] </br> dp[3 -1]\[3](=2) +dp[3]\[3-3](=1)|dp[3][3]</br>=3 
15|3|4|j - i >0 </br> 4-3 >0|dp[i-1][j] + dp[i][j-i] </br> dp[3 -1]\[4](=3) +dp[3]\[4-3](=1)|dp[3][4]</br>=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 </br> 0-1 < 0|dp[i-1][j] </br>dp[1-1][0] |dp[1][0]</br>=1
2|1|1|j - i >0 </br> 1-1 >0|dp[i-1][j] + dp[i][j-i] </br> dp[1 -1]\[1](=0) +dp[1]\[1-1](=1)|dp[1][1]</br>=1 
3|1|2|j - i >0 </br> 2-1 >0|dp[i-1][j] + dp[i][j-i] </br> dp[1 -1]\[2](=0) +dp[1]\[2-1](=1)|dp[1][2]</br>=1 
4|2|0|j - i < 0 </br> 0-2 < 0|dp[i-1][j] </br>dp[2-1][0] |dp[2][0]</br>=1
5|2|1|j - i < 0 </br> 1-2 < 0|dp[i-1][j] </br>dp[2-1][1] |dp[2][1]</br>=1
6|2|2|j - i >0 </br> 2-2 >0|dp[i-1][j] + dp[i][j-i] </br> dp[2 -1]\[2](=1) +dp[2]\[2-2](=1)|dp[2][2]</br>=2 


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



### dpの動き
![image-2 (1).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2710623/34ae2150-face-244c-9e58-caed361d6d6d.png)


## 他の例　n=3 m=3 結果値　3個
ループ数|i|j|条件|resの計算式|resの値
--|--|-----|----|-----|---
1|1|0|j - i < 0 </br> 0-1 < 0|dp[i-1][j] </br>dp[1-1][0] |dp[1][0]</br>=1
2|1|1|j - i >0 </br> 1-1 >0|dp[i-1][j] + dp[i][j-i] </br> dp[1 -1]\[1](=0) +dp[1]\[1-1](=1)|dp[1][1]</br>=1 
3|1|2|j - i >0 </br> 2-1 >0|dp[i-1][j] + dp[i][j-i] </br> dp[1 -1]\[2](=0) +dp[1]\[2-1](=1)|dp[1][2]</br>=1 
4|1|3|j - i >0 </br> 3-1 >0|dp[i-1][j] + dp[i][j-i] </br> dp[1 -1]\[3](=0) +dp[1]\[3-1](=1)|dp[1][3]</br>=1 
5|2|0|j - i < 0 </br> 0-2 < 0|dp[i-1][j] </br>dp[2-1][0] |dp[2][0]</br>=1
6|2|1|j - i < 0 </br> 1-2 < 0|dp[i-1][j] </br>dp[2-1][1] |dp[2][1]</br>=1
7|2|2|j - i >0 </br> 2-2 >0|dp[i-1][j] + dp[i][j-i] </br> dp[2 -1]\[2](=1) +dp[2]\[2-2](=1)|dp[2][2]</br>=2 
8|2|3|j - i >0 </br> 3-2 >0|dp[i-1][j] + dp[i][j-i] </br> dp[2 -1]\[3](=1) +dp[2]\[3-2](=1)|dp[2][3]</br>=2 
9|3|0|j - i < 0 </br> 0-3 < 0|dp[i-1][j] </br>dp[3-1][0] |dp[3][0]</br>=1
10|3|1|j - i < 0 </br> 1-3 < 0|dp[i-1][j] </br>dp[3-1][1] |dp[3][1]</br>=1
11|3|2|j - i < 0 </br> 2-3 < 0|dp[i-1][j] </br>dp[3-1][2] |dp[3][2]</br>=2
12|3|3|j - i >0 </br> 3-3 >0|dp[i-1][j] + dp[i][j-i] </br> dp[3 -1]\[3](=2) +dp[3]\[3-3](=1)|dp[3][3]</br>=3 

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

### dpの動き

![image-3.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2710623/03649798-3836-31b5-1e0e-2c6ad10b3b68.png)


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

ループ数|i|j|条件|resの計算式|resの値
--|--|-----|----|-----|---
1|1|0|j - i < 0 </br> 0-1 < 0|dp[i-1][j] </br>dp[1-1][0] |dp[1][0]</br>=1
2|1|1|j - i >0 </br> 1-1 >0|dp[i-1][j] + dp[i][j-i] </br> dp[1 -1]\[1](=0) +dp[1]\[1-1](=1)|dp[1][1]</br>=1 
3|1|2|j - i >0 </br> 2-1 >0|dp[i-1][j] + dp[i][j-i] </br> dp[1 -1]\[2](=0) +dp[1]\[2-1](=1)|dp[1][2]</br>=1 
4|1|3|j - i >0 </br> 3-1 >0|dp[i-1][j] + dp[i][j-i] </br> dp[1 -1]\[3](=0) +dp[1]\[3-1](=1)|dp[1][3]</br>=1 
5|1|4|j - i >0 </br> 4-1 >0|dp[i-1][j] + dp[i][j-i] </br> dp[1 -1]\[4](=0) +dp[1]\[4-1](=1)|dp[1][4]</br>=1 
6|2|0|j - i < 0 </br> 0-2 < 0|dp[i-1][j] </br>dp[2-1][0] |dp[2][0]</br>=1
7|2|1|j - i < 0 </br> 1-2 < 0|dp[i-1][j] </br>dp[2-1][1] |dp[2][1]</br>=1
8|2|2|j - i >0 </br> 2-2 >0|dp[i-1][j] + dp[i][j-i] </br> dp[2 -1]\[2](=1) +dp[2]\[2-2](=1)|dp[2][2]</br>=2 
9|2|3|j - i >0 </br> 3-2 >0|dp[i-1][j] + dp[i][j-i] </br> dp[2 -1]\[3](=1) +dp[2]\[3-2](=1)|dp[2][3]</br>=2 
10|2|4|j - i >0 </br> 4-2 >0|dp[i-1][j] + dp[i][j-i] </br> dp[2 -1]\[4](=1) +dp[2]\[4-2](=2)|dp[2][4]</br>=3 
11|3|0|j - i < 0 </br> 0-3 < 0|dp[i-1][j] </br>dp[3-1][0] |dp[3][0]</br>=1
12|3|1|j - i < 0 </br> 1-3 < 0|dp[i-1][j] </br>dp[3-1][1] |dp[3][1]</br>=1
13|3|2|j - i < 0 </br> 2-3 < 0|dp[i-1][j] </br>dp[3-1][2] |dp[3][2]</br>=2
14|3|3|j - i >0 </br> 3-3 >0|dp[i-1][j] + dp[i][j-i] </br> dp[3 -1]\[3](=2) +dp[3]\[3-3](=1)|dp[3][3]</br>=3 
15|3|4|j - i >0 </br> 4-3 >0|dp[i-1][j] + dp[i][j-i] </br> dp[3 -1]\[4](=3) +dp[3]\[4-3](=1)|dp[3][4]</br>=4 
16|4|0|j - i < 0 </br> 0-4 < 0|dp[i-1][j] </br>dp[4-1][0] |dp[4][0]</br>=1
17|4|1|j - i < 0 </br> 1-4 < 0|dp[i-1][j] </br>dp[4-1][1] |dp[4][1]</br>=1
18|4|2|j - i < 0 </br> 2-4 < 0|dp[i-1][j] </br>dp[4-1][2] |dp[4][2]</br>=2
19|4|3|j - i < 0 </br> 3-4 < 0|dp[i-1][j] </br>dp[4-1][3] |dp[4][3]</br>=3
20|4|4|j - i >0 </br> 4-4 >0|dp[i-1][j] + dp[i][j-i] </br> dp[4 -1]\[4](=4) +dp[4]\[4-4](=1)|dp[4][4]</br>=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コミット部分

https://github.com/RYA234/laravel9_vite_vue3/commit/4a044a9065f4fb555eb505559b553734950fcaa9