日記

のみろぐ

主に競プロ日記です

DPL_1_A「コイン問題」

DPL_1_A「コイン問題

考察

  • 価値の高いコインから順番に使う貪欲法で解けるのでは?
  • でも、ちょうど$n$円払いたいので、貪欲ではうまくいかない時がある。
  • 例えば、$n=10, m=4, c = {1, 4, 6, 7}$のとき。大きいほうから払っていく貪欲だと$7+1+1+1$で合計$4$手になってしまう。
  • 5円になるまでの最小手数を求める→6円になるまでの最小手数を求める→7円...みたいなことができそう。これはDPで解けるのでは?


解法

f:id:nomikura:20180613150557p:plain

  1. 上記のような1次元のDPテーブルを用意する
  2. DPテーブルを初期化する
    • dp[0]は$0$、それ以外はINFで初期化する
  3. 漸化式をコードとして書く

漸化式

$$ dp[i] = min(dp[i], dp[i-c[j]+1]) \ \ (i \geq c[j]) $$

おまけ

  • $n=5, m=3, c={1,2,3}$のとき、DPは以下のように遷移する
  • 見ている要素に最適な値が収束する感じになる。
  • DPの本質は、あるポイントに値を収束させることの繰り返しなのでわかりやすいDPなんだと思う。

f:id:nomikura:20180613150617p:plain


コード

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e8;
int n, m;
int c[22];
int dp[55555]; // dp[i]: i円になるまでのコインの最小枚数

int main() {
    // 入力
    cin >> n >> m;
    for (int i = 0; i < m; i++) { cin >> c[i]; }

    // DPテーブル初期化
    fill(dp, dp+n+1, INF);
    dp[0] = 0;

    // DP
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < m; j++) {
            if (i >= c[j]) {
                dp[i] = min(dp[i], dp[i-c[j]]+1);
            }
        }
    }
    cout << dp[n] << endl;

    return 0;
}


要点

  • DPの本質はあるポイントに値を収束させることの繰り返しであるということ。


類題


感想

  • 貪欲→DPを思いつける気がしない。
  • 上手いこと貪欲の反例が見つかれば良いけど、もっと複雑な問題だったら見つからない気がする...