Reference no: EM13165383

coin change program. Make change using fewest number of coins. I'm attempting dynamic programming and i may be misunderstanding the algorithm. When i compile, the debug assertion fails and i receive the expression: vector subscript out of range.

the algorithm i'm trying to follow is:

Input Parameters: denom,A
Output Parameter: C

dynamic_coin_change1(denom,A, C) {
n = denom.last
for j = 0 to A
C[n][j] = j
for i = n ? 1 downto 1
for j = 0 to A
if (denom[i] > j || C[i + 1][j] < 1 + C[i][j ? denom[i]])
C[i][j] = C[i + 1][j]
else
C[i][j] = 1 + C[i][j ? denom[i]]
}

My code so far is:

    #include <iostream>
    #include <vector>

    int main()
    {
        vector<int> denom{3,2,8,10};
        int n = denom.size();
        int sum = 57;
        int j = 0;
        int i = 0;
        typedef vector<vector<int>> matrix;
        matrix solVec(n,vector<int>(sum));

        for(i = n-1;i >= 1; i--)
          {
              for(j = 0; j <= sum; j++)
                {
                    if(denom[i]>j || solVec[i+1][j] < 1 + solVec[i][j - denom[i]])
                        solVec[i][j] = solVec[i+1][j];
                    else
                        solVec[i][j] = 1 + solVec[i][j - denom[i]];
                {
          }
      cout<<solVec[i][j];
      system("pause");
      return 0;