Is this variation of coin change problem solvable using DP ?

Revision en2, by X-O__O-X, 2020-12-03 18:42:06

I know how to solve the following variation;

Given list of coins c[1], c[2], ..., c[n], no 2 coins are same, and a target sum. Count number of ways to make the sum using the given coins ?

When

  • There is 1 unit of each coin

  • There is infinite supply of each coin.

I wonder what if there is a specific amount for each type of coin. so I am given the list of types of coins and the list a[1]...a[n] such that a[i] is the number of coins allowed of type c[i].

Can we solve it using DP ?

If yes, is the solution similar to the solution of the classical problem ? appreciate if you describe the whole solution.

If no, how to solve it? at least, what topics or techniques required?

Also, I would like to know generally how one prove that DP cannot solve some problem, if possible ?

Thanks for reading

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English X-O__O-X 2020-12-03 18:42:06 4
en1 English X-O__O-X 2020-12-03 18:37:11 897 Initial revision (published)