Изменение монеты 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;