DP 코인 변경 설명

Question

코인 변경은 동전 (C [0], C [1] ... C [K-1])을 사용하여 N 센트의 합계에 도달 할 수있는 방법을 묻는 매우 인기있는 문제입니다. . DP 해는 다음과 같은 방법을 사용한다. s (N, K) = s (N, K-1) + s (NC [K-1], K) 첫 번째 K 동전 (오름차순으로 정렬)과 합계 N으로 도착합니다. 첫 번째 K 동전을 사용하여 N 센트를 만드는 방법의 양은 N 번째 - K 번째 동전에 도착하는 방법의 양에 추가 된 K 번째 코인을 사용하지 않고 동일한 합계에 도달하는 방법의 양을 합한 것입니다. 나는이 솔루션을 어떻게 만날 수 있는지, 그것이 논리적으로 어떻게 의미가 있는지 이해하지 못합니다. 누군가 설명 할 수 있을까요?

Answer 1

DP를 해결할 때 가장 중요한 것은 문제를 일련의 간단한 하위 문제로 줄이는 것입니다. 대부분의 경우 "더 간단하다"는 것은 더 작은 인수를 의미하며,이 경우 합계가 적거나 나머지 코인 값이 적 으면 문제가 더 간단합니다.

문제를 해결하기위한 나의 사고 방식은 다음과 같습니다. 좋아요. 동전 세트가 있는데, 주어진 합계를 형성 할 수있는 방법의 수를 계산해야합니다. 이것은 복잡하게 들리지만, 동전이 하나 밖에 없다면 조금 더 쉬울 것입니다.

또한 하단의 경우를 생각하는 데 도움이됩니다. 이 경우에는 동전이 모두있는 경우 주어진 금액을 얼마나 많은 방법으로 형성 할 수 있는지 알 수 있습니다. 이것은 어떻게 든 단순한 문제를 줄이면 아마 다른 동전의 수를 줄일 수 있다고 제안합니다.