AOJ

# Problem

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp

# Explanation

0	10001	10001	10001	10001	10001	10001	10001	10001	10001	10001	10001	10001	10001	10001	10001
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	1	1	2	2	3	3	4	4	5	5	6	6	7	7	8
0	1	1	2	2	3	3	1	2	2	3	3	4	4	2	3
0	1	1	2	2	3	3	1	1	2	2	3	3	4	2	2
0	1	1	2	2	3	3	1	1	2	2	3	1	2	2	2
0	1	1	2	2	3	3	1	1	2	2	3	1	2	2	2


# Computational complexity

$O(MN)$

# Solution 1

Less space ( $O(N)$ )required.


#define W_MAX 10000
#define INF 10001
#define N_MAX 50001
#define M_MAX 21

Int N, M;
Int COINS[M_MAX+1];
Int table[N_MAX+1];

Int min_coin() {
loop(n,0,N+1) {
table[n] = INF;
}
table[0] = 0;

loop(m,1,M+1) {
Int coin = COINS[m];
loop(n,coin,N+1) {
table[n] = min(table[n], table[n-coin] + 1);
}
}

return table[N];
}

int main(void) {
cin >> N >> M;
COINS[0] = 0;
loop(i,1,M+1) {
cin >> COINS[i];
}

cout << min_coin() << endl;
}


# Solution 2

Require $O(MN)$ space


#define W_MAX 10000
#define INF 10001
#define N_MAX 50001
#define M_MAX 21

Int N, M;
Int COINS[M_MAX+1];
Int table[M_MAX+1][N_MAX+1];

Int min_coin() {
loop(n,0,N+1) {
table[0][n] = INF;
}
loop(m,0,M+1) {
table[m][0] = 0;
}

loop(m,1,M+1) {
Int coin = COINS[m];
loop(n,1,N+1) {
if (n - coin < 0) {
table[m][n] = table[m-1][n];
continue;
}

table[m][n] = min(table[m-1][n], table[m][n-coin] + 1);
}
}

return table[M][N];
}

int main(void) {
cin >> N >> M;
COINS[0] = 0;
loop(i,1,M+1) {
cin >> COINS[i];
}

cout << min_coin() << endl;
}


Remote freelancer. A web and mobile application enginner.
Traveling around the world based on East Asia.
I'm looking forward to your job offers from all over the world!

Offer jobs or contact me!