Let’ there are coins from 1 to N and the sum you are trying to get is SUM. Problem is basically finding in how many ways we can make the sum SUM using coins that have numbers from 1 to N.
This problem can be solved using dynamic programming. Instead of thinking about filling a matrix, think in terms of the recurrence relation. The essence of dynamic programming is the idea of a state space and a recurrence relation between states. Once you figure that out for any problem, implementation is straightforward.
In coin change problem, the state representation needs two pieces of information:
- Desired sum
- Set of coins that can be used
Now lets consider coin number 1. We will either use it or we won’t. If we don’t use that coin, the problem is basically finding out in how many ways we can make sum S using coin number 2 to N. Note that we have got an instance of the same problem, only this time the problem is even simpler, we have to consider one less coin!
Now let’s consider the other possibility. We can use coin number 1. Let the value of coin number 1 be val[1]. So if we consider the first copy of coin number 1, so our remaining desired sum is SUM – val[1]. But we may take more copies of coin 1, so the problem now becomes counting in how many ways we can get sum SUM – val[1] using coin number 1 to N. Note that again we have got an instance of the same problem and again, the problem is simpler then the previous one, we have a smaller sum to make!
Let dp[S][i] denote the number of ways in which we can make sum SUM using coin numbers i to N, so from the discussion above , we can easily find the following recurrence relation
dp[s][i] = dp[s][i+1] + val[i]<=s ? dp[ s - val[i] ] [i] : 0;