JavaScriptで蟻本 動的計画法　重複組み合わせ


# 概要
アルゴリズムを学習をした際の記録を投稿します。
今回は蟻本p67動的計画法の重複組合せについてです。


# 問題

```
n種類の品物があり、i番目の品物はai個あります。異なる種類の品物同士は区別できますが、同じ種類の品
物同士は区別できません。これらの品物の中からm個選ぶ組み合わせの総数を求め、Mで割った余りを答えなさい。

入力
n = 3
m = 3
a = [1,2,3]
M = 10000

出力
6
```





# コード部分
```javascript
//
/**
 * pp67 重複組み合わせ　
 * @param n {Number} 品物の種類
 * @param m {Number}  選ぶ個数
 * @param a{Array} i番目の個数
 * @return {Number} 組み合わせの総数
 */
const  cal = (n,m,a) =>{
    let dp = new Array(n + 1).fill(null).map(() => new Array(m + 1).fill(0));
    for(let i=0;i <= n; i++){
        dp[i][0] = 1;
    }
    let loopCount = 0;
    console.log(`ループ数|i|j|条件|dp[i+1][j]の計算式|dp[i+1][j]の値`);
    console.log(`--|--|-----|----|-----|---`);
    for(let i=0; i < n; i++){
        for(let j=1; j<=m; j++){
            loopCount++;
            if(j - 1 - a[i] >= 0){
                dp[i+1][j] = dp[i+1][j-1] +dp[i][j]-dp[i][j-1-a[i]]
                console.log(`${loopCount}|${i} | ${j} | j - 1 - a[i] >= 0 </br> ${j} - ${1} - a[${i}] ( =${a[i]}) >= 0 |  dp[i+1][j-1] +dp[i][j]-dp[i][j-1-a[i]]</br>dp[${i}+1][${j}-1]( = ${dp[i+1][j-1]}) + dp[${i}][${j}]( = ${dp[i][j]}) - dp[${i}][${j}-1-a[${i}]]( = ${dp[i][j-1-a[i]]})  | dp[${i+1}][${j}]  = ${dp[i+1][j]}`)
            }else{
                dp[i+1][j] = dp[i+1][j-1] +dp[i][j];
                console.log(`${loopCount}|${i} | ${j} | j - 1 - a[i] < 0 </br> ${j} - ${1} - a[${i}] ( =${a[i]}) < 0 |  dp[i+1][j-1] +dp[i][j]</br>dp[${i}+1][${j}-1]( = ${dp[i+1][j-1]}) + dp[${i}][${j}]( = ${dp[i][j]}) | dp[${i+1}][${j}]  = ${dp[i+1][j]}`)
            }
        }
    }
    console.log(dp);
    return dp[n][m];
}
// 結果値は結果値は6
console.log(cal(3,3,[1,2,3]));
```

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

[リンク](https://pythontutor.com/render.html#code=//%0A/**%0A%20*%20pp67%20%E9%87%8D%E8%A4%87%E7%B5%84%E3%81%BF%E5%90%88%E3%82%8F%E3%81%9B%E3%80%80%0A%20*%20%40param%20n%20%7BNumber%7D%20%E5%93%81%E7%89%A9%E3%81%AE%E7%A8%AE%E9%A1%9E%0A%20*%20%40param%20m%20%7BNumber%7D%20%20%E9%81%B8%E3%81%B6%E5%80%8B%E6%95%B0%0A%20*%20%40param%20a%7BArray%7D%20i%E7%95%AA%E7%9B%AE%E3%81%AE%E5%80%8B%E6%95%B0%0A%20*%20%40return%20%7BNumber%7D%20%E7%B5%84%E3%81%BF%E5%90%88%E3%82%8F%E3%81%9B%E3%81%AE%E7%B7%8F%E6%95%B0%0A%20*/%0Aconst%20%20cal%20%3D%20%28n,m,a%29%20%3D%3E%7B%0A%20%20%20%20let%20dp%20%3D%20new%20Array%28n%20%2B%201%29.fill%28null%29.map%28%28%29%20%3D%3E%20new%20Array%28m%20%2B%201%29.fill%280%29%29%3B%0A%20%20%20%20for%28let%20i%3D0%3Bi%20%3C%3D%20n%3B%20i%2B%2B%29%7B%0A%20%20%20%20%20%20%20%20dp%5Bi%5D%5B0%5D%20%3D%201%3B%0A%20%20%20%20%7D%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%7Cdp%5Bi%2B1%5D%5Bj%5D%E3%81%AE%E8%A8%88%E7%AE%97%E5%BC%8F%7Cdp%5Bi%2B1%5D%5Bj%5D%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%20for%28let%20i%3D0%3B%20i%20%3C%20n%3B%20i%2B%2B%29%7B%0A%20%20%20%20%20%20%20%20for%28let%20j%3D1%3B%20j%3C%3Dm%3B%20j%2B%2B%29%7B%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%20if%28j%20-%201%20-%20a%5Bi%5D%20%3E%3D%200%29%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20dp%5Bi%2B1%5D%5Bj%5D%20%3D%20dp%5Bi%2B1%5D%5Bj-1%5D%20%2Bdp%5Bi%5D%5Bj%5D-dp%5Bi%5D%5Bj-1-a%5Bi%5D%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20console.log%28%60%24%7BloopCount%7D%7C%24%7Bi%7D%20%7C%20%24%7Bj%7D%20%7C%20j%20-%201%20-%20a%5Bi%5D%20%3E%3D%200%20%3C/br%3E%20%24%7Bj%7D%20-%20%24%7B1%7D%20-%20a%5B%24%7Bi%7D%5D%20%28%20%3D%24%7Ba%5Bi%5D%7D%29%20%3E%3D%200%20%7C%20%20dp%5Bi%2B1%5D%5Bj-1%5D%20%2Bdp%5Bi%5D%5Bj%5D-dp%5Bi%5D%5Bj-1-a%5Bi%5D%5D%3C/br%3Edp%5B%24%7Bi%7D%2B1%5D%5B%24%7Bj%7D-1%5D%28%20%3D%20%24%7Bdp%5Bi%2B1%5D%5Bj-1%5D%7D%29%20%2B%20dp%5B%24%7Bi%7D%5D%5B%24%7Bj%7D%5D%28%20%3D%20%24%7Bdp%5Bi%5D%5Bj%5D%7D%29%20-%20dp%5B%24%7Bi%7D%5D%5B%24%7Bj%7D-1-a%5B%24%7Bi%7D%5D%5D%28%20%3D%20%24%7Bdp%5Bi%5D%5Bj-1-a%5Bi%5D%5D%7D%29%20%20%7C%20dp%5B%24%7Bi%2B1%7D%5D%5B%24%7Bj%7D%5D%20%20%3D%20%24%7Bdp%5Bi%2B1%5D%5Bj%5D%7D%60%29%0A%20%20%20%20%20%20%20%20%20%20%20%20%7Delse%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20dp%5Bi%2B1%5D%5Bj%5D%20%3D%20dp%5Bi%2B1%5D%5Bj-1%5D%20%2Bdp%5Bi%5D%5Bj%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20console.log%28%60%24%7BloopCount%7D%7C%24%7Bi%7D%20%7C%20%24%7Bj%7D%20%7C%20j%20-%201%20-%20a%5Bi%5D%20%3C%200%20%3C/br%3E%20%24%7Bj%7D%20-%20%24%7B1%7D%20-%20a%5B%24%7Bi%7D%5D%20%28%20%3D%24%7Ba%5Bi%5D%7D%29%20%3C%200%20%7C%20%20dp%5Bi%2B1%5D%5Bj-1%5D%20%2Bdp%5Bi%5D%5Bj%5D%3C/br%3Edp%5B%24%7Bi%7D%2B1%5D%5B%24%7Bj%7D-1%5D%28%20%3D%20%24%7Bdp%5Bi%2B1%5D%5Bj-1%5D%7D%29%20%2B%20dp%5B%24%7Bi%7D%5D%5B%24%7Bj%7D%5D%28%20%3D%20%24%7Bdp%5Bi%5D%5Bj%5D%7D%29%20%7C%20dp%5B%24%7Bi%2B1%7D%5D%5B%24%7Bj%7D%5D%20%20%3D%20%24%7Bdp%5Bi%2B1%5D%5Bj%5D%7D%60%29%0A%20%20%20%20%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%5Bn%5D%5Bm%5D%3B%0A%7D%0A//%20%E7%B5%90%E6%9E%9C%E5%80%A4%E3%81%AF%E7%B5%90%E6%9E%9C%E5%80%A4%E3%81%AF6%0Aconsole.log%28cal%283,3,%5B1,2,3%5D%29%29%3B&cumulative=false&curInstr=0&heapPrimitives=nevernest&mode=display&origin=opt-frontend.js&py=js&rawInputLstJSON=%5B%5D&textReferences=false)

# その他情報

## 感想
動的計画法に関しては漸化式を決めるのが難しいですね。
実装の方法については見慣れましたね。


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



![image-7.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2710623/cde56a77-d564-77df-4e00-d07e07f1c575.png)


## 状態遷移図
計算内容を明示する表。
ステップごとの変数の値を各列に表示します。
複雑な計算を行うコードを理解するのに役立つ表です。
ループ数|i|j|条件|dp[i+1][j]の計算式|dp[i+1][j]の値
--|--|-----|----|-----|---
1|0 | 1 | j - 1 - a[i] < 0 </br> 1 - 1 - a[0] ( =1) < 0 |  dp[i+1][j-1] +dp[i][j]</br>dp[0+1][1-1]( = 1) + dp[0][1]( = 0) | dp[1][1]  = 1
2|0 | 2 | j - 1 - a[i] >= 0 </br> 2 - 1 - a[0] ( =1) >= 0 |  dp[i+1][j-1] +dp[i][j]-dp[i][j-1-a[i]]</br>dp[0+1][2-1]( = 1) + dp[0][2]( = 0) - dp[0][2-1-a[0]]( = 1)  | dp[1][2]  = 0
3|0 | 3 | j - 1 - a[i] >= 0 </br> 3 - 1 - a[0] ( =1) >= 0 |  dp[i+1][j-1] +dp[i][j]-dp[i][j-1-a[i]]</br>dp[0+1][3-1]( = 0) + dp[0][3]( = 0) - dp[0][3-1-a[0]]( = 0)  | dp[1][3]  = 0
4|1 | 1 | j - 1 - a[i] < 0 </br> 1 - 1 - a[1] ( =2) < 0 |  dp[i+1][j-1] +dp[i][j]</br>dp[1+1][1-1]( = 1) + dp[1][1]( = 1) | dp[2][1]  = 2
5|1 | 2 | j - 1 - a[i] < 0 </br> 2 - 1 - a[1] ( =2) < 0 |  dp[i+1][j-1] +dp[i][j]</br>dp[1+1][2-1]( = 2) + dp[1][2]( = 0) | dp[2][2]  = 2
6|1 | 3 | j - 1 - a[i] >= 0 </br> 3 - 1 - a[1] ( =2) >= 0 |  dp[i+1][j-1] +dp[i][j]-dp[i][j-1-a[i]]</br>dp[1+1][3-1]( = 2) + dp[1][3]( = 0) - dp[1][3-1-a[1]]( = 1)  | dp[2][3]  = 1
7|2 | 1 | j - 1 - a[i] < 0 </br> 1 - 1 - a[2] ( =3) < 0 |  dp[i+1][j-1] +dp[i][j]</br>dp[2+1][1-1]( = 1) + dp[2][1]( = 2) | dp[3][1]  = 3
8|2 | 2 | j - 1 - a[i] < 0 </br> 2 - 1 - a[2] ( =3) < 0 |  dp[i+1][j-1] +dp[i][j]</br>dp[2+1][2-1]( = 3) + dp[2][2]( = 2) | dp[3][2]  = 5
9|2 | 3 | j - 1 - a[i] < 0 </br> 3 - 1 - a[2] ( =3) < 0 |  dp[i+1][j-1] +dp[i][j]</br>dp[2+1][3-1]( = 5) + dp[2][3]( = 1) | dp[3][3]  = 6

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


## dpテーブルの図
手書き数字はループ数
![image-5.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2710623/771905b2-01bb-1a54-d588-bcd69c5c2c39.png)


# 参考資料

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

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

# githubコミット部分

https://github.com/RYA234/laravel9_vite_vue3/commit/bbfc78238a002b9e722f5c7322d30a21e52bf4dc