Coin Change 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;