November 26, 2021

[2,3,5] 원이 있을때 11원을 만드는 방법

정답 : 3

F(11) = 11을 만드는데 필요한 동전의 최소 개수

이렇게 sub problem 으로 나누어진다

F(9) = 9를 만드는데 필요한 동전의 최소 개수

F(8) = 8를 만드는데 필요한 동전의 최소 개수

F(6) = 6를 만드는데 필요한 동전의 최소 개수

Top-down 방식

F(11) = Min( F(9), F(8), F(6) ) + 1

F(n) = Min( F(n-2), F(n-3), F(n-5) ) +1

Bottom-up 방식

F(2)=2, F(1)=1, F(-1)=-1