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
#include
int main()
{
vector denom{3,2,8,10};
int n = denom.size();
int sum = 57;
int j = 0;
int i = 0;
typedef vector> matrix;
matrix solVec(n,vector(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< system("pause");
return 0;