algorithmdynamic-programmingcoin-change# Dynamic Programming Coin Change Problems

I am having issues with understanding dynamic programming solutions to various problems, specifically the coin change problem:

"Given a value N, if we want to make change for N cents, and we have infinite supply of each of S = { S1, S2, .. , Sm} valued coins, how many ways can we make the change? The order of coins doesn’t matter.

For example, for N = 4 and S = {1,2,3}, there are four solutions: {1,1,1,1},{1,1,2},{2,2},{1,3}. So output should be 4. For N = 10 and S = {2, 5, 3, 6}, there are five solutions: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} and {5,5}. So the output should be 5."

There is another variation of this problem where the solution is the minimum number of coins to satisfy the amount.

These problems appear very similar, but the solutions are very **different**.

Number of possible ways to make change: the optimal substructure for this is **DP(m,n) = DP(m-1, n) + DP(m, n-Sm)** where DP is the number of solutions for all coins up to the mth coin and amount=n.

Minimum amount of coins: the optimal substructure for this is
**DP[i] = Min{ DP[i-d1], DP[i-d2],...DP[i-dn] } + 1** where i is the total amount and d1..dn represent each coin denomination.

Why is it that the first one required a 2-D array and the second a 1-D array? Why is the optimal substructure for the number of ways to make change not "**DP[i] = DP[i-d1]+DP[i-d2]+...DP[i-dn]**" where DP[i] is the number of ways i amount can be obtained by the coins. It sounds logical to me, but it produces an incorrect answer. Why is that second dimension for the coins needed in this problem, but not needed in the minimum amount problem?

LINKS TO PROBLEMS:

http://comproguide.blogspot.com/2013/12/minimum-coin-change-problem.html http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/

Thanks in advance. Every website I go to only explains how the solution works, not why other solutions do not work.

Solution

- Lets first talk about the number of ways,
**DP(m,n) = DP(m-1, n) + DP(m, n-Sm)**. This in indeed correct because either you can use the mth denomination or you can avoid it. Now you say why don't we write it as**DP[i] = DP[i-d1]+DP[i-d2]+...DP[i-dn]**. Well this will lead to over counting , lets take an example where n=4 m=2 and S={1,3}. Now according to your solution dp[4]=dp[1]+dp[3]. ( Assuming 1 to be a base case dp[1]=1 ) .Now dp[3]=dp[2]+dp[0]. ( Again dp[0]=1 by base case ). Again applying the same dp[2]=dp[1]=1. Thus in total you get answer as 3 when its supposed to be just 2 ( (1,3) and (1,1,1,1) ). Its so because your second method treats (1,3) and (3,1) as two different solution.Your second method can be applied to case where order matters, which is also a standard problem. Now to your second question you say that minimum number of denominations can be found out by

**DP[i] = Min{ DP[i-d1], DP[i-d2],...DP[i-dn] } + 1**. Well this is correct as in finding minimum denominations, order or no order does not matter. Why this is linear / 1-D DP , well although the DP array is 1-D each state depends on at most m states unlike your first solution where array is 2-D but each state depends on at most 2 states. So in both case run time which is ( number of states * number of states each state depends on ) is the same which is**O(nm)**. So both are correct, just your second solution saves memory. So either you can find it by 1-D array method or by 2-D by using the recurrence**dp(n,m)=min(dp(m-1,n),1+dp(m,n-Sm))**. (Just use min in your first recurrence)

Hope I cleared the doubts , do post if still something is unclear.

- How to generate uniformly distributed subintervals of an interval?
- Generating random number in a non-power-of-2 range from random bits
- Algorithm - Search and Replace a string
- Looking for a branchless algorithm for converting a specific set of 4-bit integers
- Different results for XIRR between Excel and ExcelFinancialFunctions 3.2.0
- Find four,whose sum equals to target
- A* algorithm can't find the goal in Python
- Efficiently getting all divisors of a given number
- Are there any existed API to split IEnumerable<T> to many Vector<T> in CSharp？
- Generating all divisors of a number given its prime factorization
- Efficient way to insert a number into a sorted array of numbers?
- BFS Maximize Minimum Distance from a Monster along a path
- Is there effective algorithm that will return all different combination?
- Big O of algorithm that steps over array recursively
- Modification of Dijkstra's algorithm to make it work with negative weights and its time complexity
- Traversing/Moving over an unfolded cube
- Fibonacci Recursion using Golden Ratio(Golden Number)
- Karatsuba implementation in C
- Why is O(n) better than O( nlog(n) )?
- What is Sliding Window Algorithm? Examples?
- How to write a function to navigate through a non-binary tree?
- Evenly distribute QDate values into certain number of slots
- Find max product using divide and conqure in O(n) time
- Cache-friendly sqare matrix transposition logic issue
- Why doesn't Dijkstra's algorithm work for negative weight edges?
- Fast Convertion From Adjacency List to Edge List
- I convert ASCII words into numbers but am stuck trying to decode them. How to convert 1=a, 2=b, 28=ab etc? (psudeocode okay)
- Reversing the word order in a string in place
- Trying to make a 2x2 rubik's cube solving algorithm , how do i find the solution path (DFS)?
- question about missing element in array