106Coin Change

def coinChange(coins: list[int], amount: int) -> int:
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for coin in coins:
        for x in range(coin, amount + 1):
            dp[x] = min(dp[x], dp[x - coin] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

public int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1);
    dp[0] = 0;
    for (int coin : coins)
        for (int x = coin; x <= amount; x++)
            dp[x] = Math.min(dp[x], dp[x - coin] + 1);
    return dp[amount] > amount ? -1 : dp[amount];
}

fun coinChange(coins: IntArray, amount: Int): Int {
    val dp = IntArray(amount + 1) { amount + 1 }
    dp[0] = 0
    for (coin in coins)
        for (x in coin..amount)
            dp[x] = minOf(dp[x], dp[x - coin] + 1)
    return if (dp[amount] > amount) -1 else dp[amount]
}

int coinChange(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, amount + 1);
    dp[0] = 0;
    for (int coin : coins)
        for (int x = coin; x <= amount; x++)
            dp[x] = min(dp[x], dp[x - coin] + 1);
    return dp[amount] > amount ? -1 : dp[amount];
}