動的計画法の練習でAOJ DPL_1_A コイン問題を解く - 競技プログラミング悪戦苦闘日記

f:id:hrksb5029:20210323004700p:plain
動的計画法の練習のためにAizu Online Judge DPL_1_A コイン問題を解きました。

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_A&lang=ja

額面がc1, c2,..., cm　円の　m　種類のコインを使って、 n 円を支払うときの、コインの最小の枚数を求めて下さい。各額面のコインは何度でも使用することができます。

貪欲法で、高いコインでなるべくn円を埋めることを浮かびそうですが、それが最適解とは限らないです。
サンプルの問題のように15円を1円玉, 2円玉, 7円玉, 8円玉, 12円玉, 50円玉で支払うことを考えると、
貪欲法では、12円 + 2円 + 1円で3枚となりますが、7円 + 8円で2枚が最適ということがわかります。

dpという配列で、インデックスやdpの定義をどうするか考えるときに、まずはシンプルに答えを求める時に手っ取り早いものを考えます。
求めたいのはn円支払う時の最小枚数なので、dp[i]の定義をi円を支払うときの最小枚数とします。

nは最大で50,000、コインの種類は最大で20なので、dp[1]からdp[n]までの値を事前に計算します。

dp[i]のiは最大でも求めたいn円になります。
dp[i]の初期値はなんでも良いのですが、大きめの値で計算しても届かない値にしました。intの最大値でも良いと思います。
初期値は求めたいn円を最小額のコインで必要な枚数 + 1としました。

c_arr.sort()
max_maisu = n // c_arr[0] + 1
dp = [max_maisu for _ in range(n + 1)]

あとあらかじめ、コインの金額の値にはdp[]に1を入れます。
5円玉があれば、5円を支払うのは5円玉1枚で済みます。なのでdp[5] = 1です。
dpのインデックスは最大でもnにしているのでn円を超える値は不要です。

for c in c_arr:
    # dpのインデックスは最大でもnにしているのでn円を超える値は不要
    if c <= n:
        dp[c] = 1

c円玉を使った時のことを考えると
dp[i] = dp[i - c] + 1
最小の枚数なので、dp[i] = min(dp[i], dp[i - c] + 1) となります。

最終的なコードは以下のようになりました。

n, m = map(int, input().split())
c_arr = list(map(int, input().split()))
c_arr.sort()
max_maisu = n // c_arr[0] + 1
dp = [max_maisu for _ in range(n + 1)]
for c in c_arr:
    if c <= n:
        dp[c] = 1

# dp[i] i円支払う時の最小枚数
# c円玉を使うとき
# dp[i] = dp[i - c] + 1
for i in range(1, n + 1):
    # iがコインの最小値より低ければ、パス
    if i < c_arr[0]:
        continue
    for c in c_arr:
        # i - c が0未満だと、1つ前のステップがマイナスになってしまう
        if i - c >= 0:
            dp[i] = min(dp[i], dp[i - c] + 1)
print(dp[n])