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

概要 アルゴリズムを学習をした際の記録を投稿します。 今回は蟻本p67動的計画法の重複組合せについてです。 問題 n種類の品物があり、i番目の品物はai個あります。異なる種類の品物同士は区別できますが、同じ種類の品 物同士は区別できません。これらの品物の中からm個選ぶ組み合わせの総数を求め、Mで割った余りを答えなさい。 入力 n = 3 m = 3 a = [1,2,3] M = 10000 出力 6 // /** * 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(()