Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Making change for a dollar
<?php
// Linked posts
// https://math.stackexchange.com/questions/176363/keep-getting-generating-function-wrong-making-change-for-a-dollar/176397#176397
// https://math.stackexchange.com/questions/15521/making-change-for-a-dollar-and-other-number-partitioning-problems
// Simple solution:
// Sum you need to count
$money = 4;
// Coin variants, no matter what order
$coins = [1,2];
// Init empty array of certain size
$times = array_fill(0, $money + 1, 0);
$times[0] = 1;
foreach ($coins as $coin) {
$i = 0;
$t = $money - $coin;
for (; $i <= $t; $i++) {
$times[$i + $coin] += $times[$i];
}
}
echo $times[$money];
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment