Day 004-Q2 | DP基礎（1次元）

問題

コイン問題。N種類のコイン（価値 c[0],...,c[N-1]）で金額 X 円をちょうど支払うのに必要なコインの最小枚数を求めよ。支払えない場合は -1。各コインは何枚でも使える。

入力形式

N X
c[0] c[1] ... c[N-1]

制約

$1 \le N \le 20$

$1 \le X \le 10000$

$1 \le c_i \le 1000$

入出力例

入力例 1

3 11
1 5 6

出力例 1

入力例 2

2 3
2 4

出力例 2

-1

ヒント (段階的開示)

ヒント1: 方向性

「最小枚数」最適化 → DP（動的計画法）。再帰では指数時間。

ヒント2: アプローチ

dp[j] = 金額 j 円を作る最小枚数。dp[j] = min(dp[j], dp[j - c] + 1)。

ヒント3: 誘導

INF = float('inf')
dp = [INF] * (X + 1)
dp[0] = 0
for j in range(1, X + 1):
    for c in coins:
        if j >= c and dp[j - c] != INF:
            dp[j] = min(dp[j], dp[j - c] + 1)

模範解答 (Python)

import sys
input = sys.stdin.readline

def solve():
    N, X = map(int, input().split())
    coins = list(map(int, input().split()))

    INF = float('inf')
    dp = [INF] * (X + 1)
    dp[0] = 0

    for j in range(1, X + 1):
        for c in coins:
            if j >= c and dp[j - c] != INF:
                dp[j] = min(dp[j], dp[j - c] + 1)

    print(dp[X] if dp[X] != INF else -1)

solve()

Step-by-Step 解説

1DPの状態設計
dp[j] = 金額 j 円を作る最小コイン枚数。dp[0] = 0、他は INF で初期化。

2遷移
「金額 j を作る」=「コイン c を1枚使い、残り (j-c) を最小枚数で作る」。

3テーブル例
coins=[1,5,6], X=11 → dp[11] = min(dp[10]+1, dp[6]+1, dp[5]+1) = 2。

よくあるミス

ミス	原因	正しい書き方
dp[0] 初期化なし	全部INF	dp[0] = 0 が基底ケース
INF + 1 で不正値	チェックなし	`dp[j-c] != INF` をチェック
貪欲法で解く	コイン問題は貪欲不可なケースあり	DPを使う

Day 004-Q2 — DP基礎（1次元）

問題