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 wander 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, would like to know generally how one prove that DP cannot solve some problem, if possible ?

Thanks for reading