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, c, ..., 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...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 X-O__O-X 2020-12-03 18:42:06 4
en1 X-O__O-X 2020-12-03 18:37:11 897 Initial revision (published)