코인 변경 C++

Question

나는 동전 교환 문제를 해결할 수있는 최소한의 동전 개수를 계산하려고했습니다. 나는 http://www.algorithmist.com에 알고리즘 포스트를 사용했다. 알고리즘은 다음과 같습니다.

C(N,m) = min(C(N,m - 1),C(N - Sm,m) + 1) 

with the base cases: 

    C(N,m) = 1,N = 0 
    C(N,m) = 0,N < 0 
    C(N, m) = 0, N >= 1, m <= 0 

그러나 코드를 작성하면 무한대로 실행됩니다.

#include <iostream> 
#include <algorithm> 
using namespace std; 
int Types[101]; 
int Coins(int N, int m) 
{ 
    if(N==0) 
    { 
     return 1; 
    } 
    else if(N<0) 
    { 
     return 0; 
    } 
    else if(N>0 && m<=0) 
    { 
     return 0; 
    } 
    else 
    { 
     int a = Coins(N,m-1); 
     int b = Coins(N-Types[m],m) + 1; 
     int c = min(a,b); 
     return c; 
    } 
} 

int main() 
{ 
    int noOfCoins, Target; 
    cin >> noOfCoins >> Target; 
    for(int i = 0; i<noOfCoins; i++) 
    { 
     cin >> Types[i]; 
    } 
    cout << Coins(Target, noOfCoins); 
    return 0; 
} 

것은 무엇 잘못 될 수 있습니다 여기에

코드인가?

Answer 1

이 cout << Coins(Target, noOfCoins - 1);

대신 cout << Coins(Target, noOfCoins);

그렇지 않으면 당신이 0 요소를 액세스, 그리고 다시 여기에 다시 같은 상태로 이동해야합니다

이

int b = Coins(N-Types[m],m) + 1;