3 6
1 2 3
- N=3, K=6
- 数列A =
[1, 2, 3]
dp[k] = kを作るための最小個数
初期状態：
k: 0 1 2 3 4 5 6
-----------------------
dp: 0 ∞ ∞ ∞ ∞ ∞ ∞
dp[0]=0（0は何も選ばずに作れる）- 他は
Infinity（まだ作れない）
使う場合：
更新対象は、k=6→1 まで逆順にチェック。
dp[1] = min(dp[1], dp[1-1] + 1)
→ dp[1] = min(∞, 0+1) = 1
更新後：
k: 0 1 2 3 4 5 6
-----------------------
dp: 0 1 ∞ ∞ ∞ ∞ ∞
更新対象は、k=6→2。
- k=2
dp[2] = min(dp[2], dp[2-2]+1)
→ dp[2] = min(∞, 0+1) = 1
- k=3
dp[3] = min(dp[3], dp[3-2]+1)
→ dp[3] = min(∞, 1+1) = 2
- k=4
dp[4] = min(dp[4], dp[4-2]+1)
→ dp[4] = min(∞, ∞+1) = ∞
- k=5,6：変化なし
更新後：
k: 0 1 2 3 4 5 6
-----------------------
dp: 0 1 1 2 ∞ ∞ ∞
更新対象は、k=6→3。
- k=3
dp[3] = min(dp[3], dp[3-3]+1)
→ dp[3] = min(2, 0+1) = 1
- k=4
dp[4] = min(dp[4], dp[4-3]+1)
→ dp[4] = min(∞, 1+1) = 2
- k=5
dp[5] = min(dp[5], dp[5-3]+1)
→ dp[5] = min(∞, 1+1) = 2
- k=6
dp[6] = min(dp[6], dp[6-3]+1)
→ dp[6] = min(∞, 2+1) = 3
k: 0 1 2 3 4 5 6
-----------------------
dp: 0 1 1 1 2 2 3
dp[6]=3（1+2+3の全てを使うと6になる）
答え：
3
初期:
[0][∞][∞][∞][∞][∞][∞]
1を使う:
[0][1][∞][∞][∞][∞][∞]
2を使う:
[0][1][1][2][∞][∞][∞]
3を使う:
[0][1][1][1][2][2][3]
┌─> 6 (使えない→更新なし)
│
├─> 5 (使えない→更新なし)
│
初期 → 4 (∞→2 に更新される 2+2)
│
├─> 3 (2→1 に更新される 3のみ)
│
├─> 2 (1→1 変化なし)
│
└─> 1 (1→1 変化なし)
-
時間計算量：
O(N × K)→ 最大約 200万回ループ -
メモリ使用量：
O(K)→ dp配列サイズ 約16KB
このアルゴリズムは**部分和問題の拡張（最小個数版）**で、 ナップサックDPの典型問題です。
- 使う/使わないを選択するため逆ループ
- 最小個数を求めるため、minを使う