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.
<?phpfunctiongetWays($n,$c){// Initialize an array to store the number of ways to make change// Set the base case: there's 1 way to make change for 0$ways=array_fill(0,$n+1,0);$ways[0]=1;// Iterate through each coinforeach($cas$coin){// Update the ways array for each value from the coin to the target amountfor($i=$coin;$i<=$n;$i++){$ways[$i]+=$ways[$i-$coin];}}// Return the number of ways to make change for the target amountreturn$ways[$n];}?>
Explanation:
Initialization: The getWays function initializes an array $ways with zeros and sets ways[0] to 1 because there's exactly one way to make change for 0 (using no coins).
Dynamic Programming: It then iterates over each coin in the given denominations. For each coin, it updates the $ways array by adding the number of ways to make change for the amount minus the coin's value.
Result: Finally, the number of ways to make change for the target amount n is returned.
Input Format:
The input is read from php://stdin:
- The first line contains two space-separated integers n and m:
- n is the amount to change.
- m is the number of different coin denominations.
- The second line contains m space-separated integers representing the coin denominations.
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 →
Explanation:
getWays
function initializes an array$ways
with zeros and setsways[0]
to 1 because there's exactly one way to make change for 0 (using no coins).$ways
array by adding the number of ways to make change for the amount minus the coin's value.n
is returned.Input Format:
The input is read from
php://stdin
: - The first line contains two space-separated integersn
andm
: -n
is the amount to change. -m
is the number of different coin denominations. - The second line containsm
space-separated integers representing the coin denominations.