Coins - Find minimum number of coins needed to hit target (denominations can be reused)

coins.php

<?php
function mincoins(array $coins, int $target): int
{
    // Check the simplest answers first...
    if (count($coins) === 0) {
        return 0;
    }

    if (in_array($target, $coins)) {
        return 1;
    }

    // Strip any duplicate coins, or coins higher than the target value...
    $coins = array_unique($coins);
    $coins = array_filter($coins, fn (int $coin): bool => $coin <= $target);

    // Sort the coins from highest to lowest...
    rsort($coins);

    // Keep adding up the given coins until the target is reached or exceeded...
    // If you changed $used to an array and put each coin in it, the method could return the exact coins needed to give as change...
    $attempt = function (array $coins) use ($target) {
        $used = 0;
        $total = 0;

        foreach ($coins as $coin) {
            while ($total + $coin <= $target) {
                $used += 1;
                $total += $coin;
            }
        }

        return ['used' => $used, 'total' => $total];
    };

    // Work through all the coins, each time removing the highest coin from the array...
    foreach (range(0, count($coins)) as $index) {
        $result = $attempt(array_slice($coins, $index));

        // As soon as we've hit the target we've got the minimum number of coins...
        if ($result['total'] === $target) {
            return $result['used'];
        }
    }

    // Otherwise we can't possibly hit the target...
    return -1;
}

echo mincoins([2, 5, 4], 8) . PHP_EOL; // Should be 2...
echo mincoins([100, 10_000, 5, 10], 115) . PHP_EOL; // Should be 3...
echo mincoins([6], 7) . PHP_EOL; // Should be -1...
echo mincoins([100, 5, 10, 15, 1, 2, 3, 4], 110) . PHP_EOL; // Should be 2...
echo mincoins([10, 3, 50], 115) . PHP_EOL; // Shoud be 7...
echo mincoins([1, 3, 5, 7], 16) . PHP_EOL; // Should be 4...

// This solution doesn't work properly, as some coin combos won't be solved.
// Proper solution is this algorithm: https://www.geeksforgeeks.org/find-minimum-number-of-coins-that-make-a-change/
// Dynamic Programming - Ch11 of Grokking Algorithms (2nd Edition)

duckduckgo_chatgpt.txt

The Minimum Coins Problem is a classic problem in dynamic programming where the goal is to find the minimum number of coins needed to make a certain amount of money using a given set of coin denominations. Here's how you can solve it using dynamic programming:

Problem Statement
Given a set of coin denominations and a total amount, find the minimum number of coins needed to make that amount. If it is not possible to make that amount with the given denominations, return -1.

Dynamic Programming Approach
Define the Problem: Let dp[i] be the minimum number of coins needed to make the amount i.
Initialization:
Set dp[0] = 0 because no coins are needed to make the amount 0.
Set dp[i] = ∞ for all other amounts i from 1 to the target amount, indicating that those amounts are initially unreachable.
Recurrence Relation: For each coin in the denominations, update the dp array:
For each amount i from the coin value to the target amount, update: dp[i]=min(dp[i],dp[i−coin]+1) This means that if we can make the amount i - coin, then we can make i by adding one more coin.
Final Result: After filling the dp array, if dp[amount] is still ∞, return -1 (indicating that the amount cannot be formed). Otherwise, return dp[amount].
Implementation
Here is a Python implementation of the above approach:

python

Copy Code
def min_coins(coins, amount):
    # Initialize the dp array
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0  # Base case: 0 coins are needed to make amount 0

    # Fill the dp array
    for coin in coins:
        for i in range(coin, amount + 1):
            dp[i] = min(dp[i], dp[i - coin] + 1)

    # Check the result
    return dp[amount] if dp[amount] != float('inf') else -1

# Example usage
coins = [1, 2, 5]
amount = 11
print(min_coins(coins, amount))  # Output: 3 (11 = 5 + 5 + 1)
Explanation of the Example
In the example above, with coin denominations of 1, 2, and 5, to make the amount 11, the minimum number of coins needed is 3 (using two 5s and one 1).

Complexity
Time Complexity: O(n * m), where n is the number of coin denominations and m is the target amount.
Space Complexity: O(m) for the dp array.
This approach efficiently computes the minimum number of coins needed to make a given amount using dynamic programming.