제한된 동전으로 변경하기위한 알고리즘 나누기 및 정복

Question

이 알고리즘은 십진, 센트, 페니 만 사용하여 입력 금액을 변경할 수있는 방법을 찾아야합니다. 나의 접근 방식은 나누기와 정복 전략을 사용하고 가장 큰 동전, 십센트 및 동전을 사용하지 않고 변경하는 방법의 수를 변경하는 방법의 수를 찾아 문제를 분리하는 것이 었습니다. 이 알고리즘에 대한 구현을 작성하여 1 ... 14의 입력에 대해 문제를 올바르게 해결하지만 입력이 15보다 크거나 같으면 반환 된 결과가 올바르지 않습니다. 분명히 내 알고리즘이 잘못되어 코드를 수정하기 위해 어떤 변화가 필요하며 내 접근법이 적절한 분할 및 정복 솔루션인지 궁금합니다.

public static int makeChange(int n) { 

     if(n < 0) 
      return 0; 
     else { 

     int sum = makeChange(n-10) + makeChange(n-5) + 1; 

     return sum; 
    } 
} 

많은 감사를 다음과 같이

코드입니다.

Answer 1

힌트 :

int nways_10 (int n) { 
    int s = 0; 
    int d = n/10; 

    for (int i = 0; i <= d; ++i) { 
     s += nways_5 (n - 10*i); 
    } 

    return s; 
} 

당신은 필요한 경우, nways_5 및 기타 함수를 작성하는 방법을 생각을 얻어야한다.

Answer 2

당신은 여기 내 대답에서 기본 알고리즘을 얻을 수 있습니다 : https://stackoverflow.com/questions/19440228/creating-a-function-that-returns-combinations-of-change/19440582#19440582

당신이