部分和問題 2 💡

今回は paiza のDPで「部分和問題 2」に挑戦！

昨日のコードに少し手を加えたらいけると思ったら大間違いだった(´;ω;｀)

余計な思い込みなしで、まっさらな気持ちで挑戦するべきだった。

問題概要

n 個のおもりのうちいくつかを選んで、重さの合計がちょうど x になる選び方が何通りあるかを求める。

※条件：

• 同じ重さのものが複数あってもそれぞれ区別する。

• 同じおもりは1回しか使えない。

• 答えは非常に大きくなる可能性があるので、答えを 1,000,000,007 で割った余りで出力する。

入力例：

5 10
7
3
4
3
2

出力例：

3

❌ NG例：

const rl = require('readline').createInterface({ input:process.stdin });

const lines = [];

rl.on('line', (input) => lines.push(input));

rl.on('close', () => {
    const [n, x] = lines[0].split(' ').map(Number);
    const a = lines.slice(1).map(Number);
    a.unshift(0);
    
    const dp = Array(x+1).fill(false);
    dp[0] = true;
    
    const arrSum = [];
    for (let i = 1; i <= n; i++) {
        for (let j = x; j >= a[i]; j--) {
            if (dp[j-a[i]]) {
                dp[j] = true;
                arrSum.push(j);
            }
        }
    }
    
    const result = arrSum.filter(sum => sum === x).length % 1000000007;
    console.log(result);
});

arrSum.push(j) は部分和ができた瞬間しか記録しない

→どのような経路でその和ができたか区別できないため、
組み合わせの重複や漏れが発生する。

前回のコードに少し手を加えたらいけそうと思ってやったらだめだった(´;ω;｀)

しかも、しばらく部分和問題「2」だから、前回コードを工夫すれば解けると思い込んで、dpの定義や前提を考え直さなかったから余計に時間がかかった(´;ω;｀)

✅ OK例：

const rl = require('readline').createInterface({ input: process.stdin });
const lines = [];

rl.on('line', (input) => lines.push(input));
rl.on('close', () => {
    const [n, x] = lines[0].split(' ').map(Number);
    const a = lines.slice(1).map(Number);

    const MOD = 1000000007;
    const dp = Array(x+1).fill(0);
    dp[0] = 1;  // 重さ0の作り方は1通り（何も選ばない）

    for (let i = 0; i < n; i++) {
        for (let j = x; j >= a[i]; j--) {
            dp[j] = (dp[j] + dp[j - a[i]]) % MOD;
        }
    }

    console.log(dp[x]);
});

• dp[j] = 「重さ j を作る方法の数」

• 各おもり a[i] を順番に見ていき、

  • おもり i の重さが a[i] なので、残りは j - a[i] になるおもりの組み合わせが何通りあるか、"存在するか"確認する。

  • これは「おもり i を使う前」の通り数 = dp[j - a[i]]

  • そこに “おもり i を足す” ことで、新たに dp[j - a[i]] 通り 増える

  • これを、おもり i を使わない もともとの方法数 dp[j] に足す

• これをすべての i に対して行うことで、すべての部分和の通り数が正しくカウントできる。

例えば、 n = 5, x = 10, a = 7 ...　のとき、

• 1個目のおもり a[1] = 7

• j を大きい方から回す（10→7）

(j = 7) → (dp[7] = 0) → (dp[7-7] = dp[0] = 1) 
   ↓         ↓　　　　　  ↓
→ dp[7]  =   0     +    1        → 1通り増える

のように各おもりで足していく。

🔍 考え方の流れ

1️⃣ dp[j] の意味

• 「重さ j を作る方法の数」

• たとえば dp[5] = 3 なら、「合計 5 になる組み合わせが 3 通りある」ということ。

2️⃣ おもり a[i] を1つ見るとき

① dp[j] → dp[j] をつくれる もともとの "古い組み合わせ" の数


② a[i] を加える前に j - a[i] を作れる組み合わせ」がそのまま "新しい組み合わせ" になる


③つまり dp[j - a[i]] を dp[j] に足す

3️⃣ 漸化式（更新）

dp[j] = dp[j] + dp[j - a[i]]

「もともとの方法数 (dp[j])」に、
「a[i] を足すことで生まれる新しい方法数 (dp[j - a[i]])」を加算。

🔍 直感的イメージ

🪵 積み木のように考える

たとえば「高さ 10 cmを作る」ことを考える。

つみ木 3 cm を使いたいとき → まず「つみ木 7 cmを作れる組み合わせ」を探す。

その組み合わせ（7cm）の後ろに「+3cm」を足せば、「10cmを作れる新しい組み合わせ」になる。

🔍 なぜ j を大きい方から回す？

小さい方から回すと、「同じおもりをすぐに再利用してしまう」から。

例：a[i]=3 のとき

• j=3 → dp[3] += dp[0] → dp[3] が更新される

• j=6 → dp[6] += dp[3]（←今更新したばかりの dp[3] を参照してしまう）

• これだと「同じ3を何度も使う」計算になってしまう。

だから 大きい方から更新して、「まだ更新されていない古い dp[j - a[i]]」を参照する必要がある。

🗒️ まとめ

• dp[j] が「もともとあった方法数」（重さ j を作る方法の数）

• dp[j - a[i]] が「新しく a[i] を使うことで追加される方法数」

• dp[j] = dp[j] + dp[j - a[i]] は「新しいおもりを加えた分の通り数を足す」式。

• ループの順序を大きい方からにするのは「同じおもりを使い回さないため」。

僕の失敗談(´;ω;｀)と解決法🐈