Tamflexの貯蔵庫

やる気のない備忘録

aoj DPL_1_A

Coin Changing Problem | Aizu Online Judge
コイン問題
貪欲法では解けないのでDPを使う.
dp[i][j] := (i枚目までのコインを使った時の金額jの最小実現枚数)
とすれば計算量O(nm)で解ける

#include <bits/stdc++.h>

#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define INF 1 << 30

using namespace std;

int main()
{
  int n, m; cin >> n >> m;
  vector<int> c(m);
  vector<int> T(n+1,INF);
  T[0] = 0;
  REP(i,m) cin >> c[i];
  REP(i,m) FOR(j,c[i],n)
    T[j] = min(T[j],T[j-c[i]]+1);
  cout << T[n] << endl;
}