私の次のコードに間違っています

Question

私はコイン変更アルゴリズムを書いています。アルゴリズムは以下のhttp://ace.cs.ohiou.edu/~razvan/courses/cs404/lecture19.pdf

から取得され、今までの私のコードです：入力2349と2102答えを

#include <vector> 
#include <iostream> 
#include <string> 

int compute_change(std::vector<int> &d, int n) { 
    int k = (int)d.size(); 
    std::vector<std::vector<int> > C(k, std::vector<int>(n + 1)); 
    for (int i = 0; i < k ; i++) 
     C[i][0] = 0; 
    for (int i = 1; i <= n ; i++) 
     C[0][i] = i; 

    for (int i = 1 ; i < k; i++) { 
     for (int j = 1 ; j <= n; j++) { 
      if (j < d[i]) 
       C[i][j] = C[i - 1][j]; 
      else 
       C[i][j] = std::min(C[i - 1][j], 1 + C[i][j - d[i]]); 
     } 
    } 
    std::cout << C[k - 1 ][n - 1] << std::endl; 
    return C[k - 1][n - 1]; 
} 

int main (int argc, char **argv) { 
    int points[] = {2, 3, 17, 23, 42, 98}; 
    std::vector<int> d (points, points + sizeof(points)/sizeof(int)); 

    int solution = compute_change(d,2349); 
    solution  = compute_change(d,2102); 
    solution  = compute_change(d,2001); 
    solution  = compute_change(d,1747); 

    return 0; 
} 

は正しいですが、2001答えを間違っています。 ここでバグを見つけることができません。

Answer 1

アルゴリズムで使用されているC++配列と1ベースのインデックスの0ベースのインデックスが混在しているようです。つまり、アルゴリズム内のd[1]はこのコードではd[0]です。しかし、いくつかの場所では、0ベースのインデックスも使用しました。すべての配列インデックスをダブルチェックすることができます。