、部分和問題（Subset Sum Problem）をDPで解く方法について、処理の流れを図解付きで丁寧に解析・説明します。

整数列 a = [a₁, a₂, ..., aₙ] の中からいくつかを選んで、ちょうど合計 K を作れるか？ 作れるなら Yes、作れなければ No を出力。

• dp[i][j] = true → 先頭から i 個目までの要素を使って、合計 j を作ることができるか？

N = 3, K = 6
a = [1, 2, 3]

最初は「何も選ばなければ合計は0」のみが成立。

dp[0][0] = true
それ以外の dp[0][j] = false (1 <= j <= K)

i=0:
j →   0   1   2   3   4   5   6
     [T   F   F   F   F   F   F]

前の行 dp[0][j] の情報をもとに dp[1][j] を更新

• dp[0][0] = true
  • dp[1][0] = true（1を使わない）
  • dp[1][1] = true（1を使う → 0+1）

i=1:
j →   0   1   2   3   4   5   6
     [T   T   F   F   F   F   F]

• dp[1][0] = true

  • → dp[2][0] = true（使わない）
  • → dp[2][2] = true（使う）

• dp[1][1] = true

  • → dp[2][1] = true（使わない）
  • → dp[2][3] = true（使う）

i=2:
j →   0   1   2   3   4   5   6
     [T   T   T   T   F   F   F]

• dp[2][0] = true

  • → dp[3][0] = true
  • → dp[3][3] = true

• dp[2][1] = true

  • → dp[3][1] = true
  • → dp[3][4] = true

• dp[2][2] = true

  • → dp[3][2] = true
  • → dp[3][5] = true

• dp[2][3] = true

  • → dp[3][3] = true
  • → dp[3][6] = true ← ここが最終的に重要！

i=3:
j →   0   1   2   3   4   5   6
     [T   T   T   T   T   T   T]

• dp[3][6] == true → Yes（合計6を作ることが可能）

行: i = 選んだ要素数（0～3）
列: j = 目標合計（0～K）

     j →  0   1   2   3   4   5   6
i=0:     T   F   F   F   F   F   F
i=1:     T   T   F   F   F   F   F
i=2:     T   T   T   T   F   F   F
i=3:     T   T   T   T   T   T   T

[dp[0][0] = true]
 ├─(使わない)→ dp[1][0]
 └─(使う+1) → dp[1][1]
      ├─(使わない)→ dp[2][1]
      └─(使う+2) → dp[2][3]
           ├─(使わない)→ dp[3][3]
           └─(使う+3) → dp[3][6] ← Yes!

• a[i] は 1〜100 なので、K=2000 のときでも範囲内に収まる。
• 状態数は N × K、最大でも 20 × 2000 = 40000 なので余裕。

• DPテーブル dp[i][j] により部分和を段階的に構築。
• 最終的な dp[N][K] を見て Yes/No を判定。
• 各ステップで「選ぶ or 選ばない」の2択を網羅的に考える。