As a homework exercise our professor presented to us a simplified version of the coin-changing problem in which we do not need to minimize the number of coins used or track the number of possible combinations. Instead we need only to determine if a certain subset of coins of same or varying denomination, equal exactly to, some amount M.
My recursion equation of the problem is as follows:
let k = 0
If ∑ (v1 + v2 + … + vn) = M
return true
If ∑ (v1 + v2 + … + vn) < M
return false
Else
Increment k by 1
make recursive call on coin subset {v1, v2, … v(n-k)}
The next question is to convert this into pseudo-code that represents a dynamic programming solution to this problem.
I'm a bit stuck. If you were to make a table of every possible sum {v1 + v2}, {v1 + v2 + v3}, {v1 + v2 + v3 + v4}, etc. You could eventually find a solution but wouldn't that be a much less efficient brute force approach?
I assume the solution would include some implementation of memoization or some way to store and retrieve sums already encountered, but being that the problem is not an optimization problem, I'm having a hard time envisioning a dynamic solution.
Much of the dynamic programming examples that I see suggest iteratively subtracting elements, one item at a time, which is similar to the composition of my recursion equation but I don't see a modification that would make this pseudo code dynamic in nature.
If anyone could please enlighten me, I'd be very grateful