We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
The solution to this problem is a good example of an efficient and tight Dynamic Programming algorithm. For those of you who are struggling with it, here's a tip. The number of ways you can make change for n using only the first m coins can be calculated using:
(1) the number of ways you can make change for n using only the first m-1 coins.
(2) the number of ways you can make change for n-C[m] using the first m coins (where C is the array of coins).
This data allows you to build the recurrence relation.
The Coin Change Problem
You are viewing a single comment's thread. Return to all comments →
The solution to this problem is a good example of an efficient and tight Dynamic Programming algorithm. For those of you who are struggling with it, here's a tip. The number of ways you can make change for n using only the first m coins can be calculated using:
(1) the number of ways you can make change for n using only the first m-1 coins.
(2) the number of ways you can make change for n-C[m] using the first m coins (where C is the array of coins).
This data allows you to build the recurrence relation.