코인 교환 - DP

Question

동적 프로그래밍의 동전 교환 문제를 이해하는 데 약간의 문제가 있습니다. 간단히 말하면, 최소 동전 수를 사용하여 금액을 변경해야합니다.

나는 1 = vv2 < ... < vn의 동전을 n 개 보유하고 있으며 금액 j를 변경하는 데 필요한 최소 동전 수를 M (j)이라고합니다.

위의 공식에서 나는 M (j-vi)가 무엇을 의미하는지 이해하지 못합니다. vi는 j-1에 사용 된 동전의 최대 값이어야합니까?

Answer 1

당신은 M (j)라는 다른 값 j에 대해 동전 더미를 만들고 있습니다. M (j - v _i)의 포인트는 값이 _{인 i}의 동전을 고려한 다음 값 j에 도달하기 위해 어느 더미에 추가합니까? 가치 j - v _i 더미는 물론 당신이 고려하고있는 동전에 j 값을 더하기 때문입니다. 물론

목표는 가능한 동전 한 적은 것입니다, 그래서 당신은 당신이 그것에 V _내가에게의 동전을 추가하여 값 j에 도달하기 위해 확장 할 수있는 가장 작은 더미를 취할. 그것이 min의 기능입니다. +1 동전 더미 _i을 더미에 추가하여 새로운 더미 M (j)을 형성했기 때문에 +1.

Answer 2

더하기 하나는 동전을 하나 더 소비한다는 의미이며 추가 된 동전의 양에 따라 총 변경액이 감소하므로 원래 j 값이 감소합니다.