알고리즘 다이나믹프로그래밍 동전 문제 1

다이나믹프로그래밍을 공부하기 좋은 기본적인 문제가 동전 문제이다.

지난번 포스팅에는 목표 금액을 만들기 위한 최소의 동전의 개수를 구하는 방법에 대해 정리해보았다.

이번 포스팅에서는 목표 금액을 만들 수 있는 모든 경우의 수를 구하는 방법에 대해서 정리해보려고 한다.

다이나믹프로그래밍은 다이나믹테이블을 만들면 쉽게 점화식을 유도해낼 수가 있다.
이번 문제의 다이나믹테이블은 다음과 같다.

	0	1	2	3	4	5	6	7	8	9	10	<- 목표 금액
1	1	1	1	1	1	1	1	1	1	1	1	<- 1원으로 목표 금액을 만들 수 있는 경우의 수
1,2	1	1	2	2	3	3	4	4	5	5	6	<- 1원, 2원으로 목표 금액을 만들 수 있는 경우의 수
1,2,5	1	1	2	2	3	4	5	6	7	8	10	<- 1원, 2원, 5원으로 목표 금액을 만들 수 있는 경우의 수