AOJ DPL1_A - Coin Changing Problem

DP力を高めるためにせっかくいい問題集があるのだから使ってみるという試み。今日からこれをやっていこうと思う。2日後にはコンテストなわけだが。。。

・問題
Coin Changing Problem | Aizu Online Judge

c1,c2, ... ,cm円というm種類のコインを使い、n円を支払うために必要なコインの枚数の最小値を求める。(必ず1円が含まれるので解はみつかる)

・考え方
dp[i]をi円を支払うために必要なコインの最小枚数とおく。すると答えはdp[n]で表される。
今累積された金額がx円である時に、そこからコインを1枚だけ出してなりうる金額は、x+c1,x+x2, ... , x+cm円のm種類のうちどれかになる。つまり、x+ci円支払うのに必要な最小枚数は、
dp[x+ci](その時点での最小枚数)またはdp[x]+1(x円での最小枚数から1枚増えたもの)
のどちらかになる。よって、
dp[x+ci] = min(dp[x+ci], dp[x]+1)
がわかる。これを小さい方からloopさせる。

これ前やったことあったかも...って問題だったからすんなり思いついたのかもしれない。これから次々やってく。

・実装(C++)

#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;

int main(){
	int n, m, c[20];
	//input
	scanf(" %d %d", &n, &m);
	for(int i=0; i<m; ++i) scanf(" %d", &c[i]);	
	
	//solve
	
	//dp[i]:=i円を支払うために必要なコインの最小枚数
	int dp[50001] = {0};
	//十分に大きい数で初期化
	for(int i=1; i<=50000; ++i) dp[i] = 100000;
	
	for(int i=0; i<=50000; ++i){
		for(int j=0; j<m; ++j){
			if(i+c[j]<=n){
				dp[i+c[j]] = min(dp[i+c[j]],dp[i]+1);	
			}
		}	
	}
	
	printf("%d\n", dp[n]);
}