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 ?
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