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.
From my understanding, this method works by taking each coin and initializing its position in the 'dp' array by one as that is one new way that value can be reach. Then for each incremental value until the desired change value, it is adding however many ways there are to get to that incremented value using the number of ways in the 'dp' array to get to the value without the coin, as adding the coin would extend all those ways to get to the previous value to the new incremented value.
For example, in the example c=[2,5,3,6] and n=10, there is no way to get the 1 coin value, so that position in the array stays 0. Because of this, the 2 coin can only increase every increment of 2 to get to the 10 value, as there is no way for the 2 coin to be used to achieve any odd number values alone. The 5 coin is then able to increment the 5 value by 1, as it is a new way to achieve that value from 0. Again, there is no 1 coin so it cannot achieve the value of 6 with the 5 coin, but it can achieve 7 and 9 with the 2 coins at values 2 and 4, so locations 7 and 9 now have 1 way to be achieved. Because of this implementation, it does not require the coins to be sorted from smallest to largest as they would stack in the final order no matter which way they were tested. For example, you would still get 1 way to get to the value of 8, whether you tested for the 5 coin and then the 3 coin or vice versa.
The code can be changed a little to make it so you’re not having to access the coin value from the array in every loop. Let me know what you think.
arr = [1]+[0]*n
for coin in c:
for value in range(coin, n+1):
arr[value] += arr[value-coin]
return arr[-1]
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
The Coin Change Problem
You are viewing a single comment's thread. Return to all comments →
From my understanding, this method works by taking each coin and initializing its position in the 'dp' array by one as that is one new way that value can be reach. Then for each incremental value until the desired change value, it is adding however many ways there are to get to that incremented value using the number of ways in the 'dp' array to get to the value without the coin, as adding the coin would extend all those ways to get to the previous value to the new incremented value.
For example, in the example c=[2,5,3,6] and n=10, there is no way to get the 1 coin value, so that position in the array stays 0. Because of this, the 2 coin can only increase every increment of 2 to get to the 10 value, as there is no way for the 2 coin to be used to achieve any odd number values alone. The 5 coin is then able to increment the 5 value by 1, as it is a new way to achieve that value from 0. Again, there is no 1 coin so it cannot achieve the value of 6 with the 5 coin, but it can achieve 7 and 9 with the 2 coins at values 2 and 4, so locations 7 and 9 now have 1 way to be achieved. Because of this implementation, it does not require the coins to be sorted from smallest to largest as they would stack in the final order no matter which way they were tested. For example, you would still get 1 way to get to the value of 8, whether you tested for the 5 coin and then the 3 coin or vice versa.
The code can be changed a little to make it so you’re not having to access the coin value from the array in every loop. Let me know what you think.