Fewest coins to make an amount

def coin_change(coins, amount):
    INF = amount + 1                      # a value no real answer can reach
    best = [0] + [INF] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and best[a - c] + 1 < best[a]:
                best[a] = best[a - c] + 1
    return -1 if best[amount] == INF else best[amount]

#include <vector>

int solve(const std::vector<int>& coins, int amount) {
    const int INF = amount + 1;                  // never a real answer
    std::vector<int> best(amount + 1, INF);
    best[0] = 0;
    for (int a = 1; a <= amount; ++a)
        for (int c : coins)
            if (c <= a && best[a - c] + 1 < best[a])
                best[a] = best[a - c] + 1;
    return best[amount] == INF ? -1 : best[amount];
}

class Solution {
    public int coinChange(int[] coins, int amount) {
        final int INF = amount + 1;
        int[] best = new int[amount + 1];
        java.util.Arrays.fill(best, INF);
        best[0] = 0;
        for (int a = 1; a <= amount; a++)
            for (int c : coins)
                if (c <= a && best[a - c] + 1 < best[a])
                    best[a] = best[a - c] + 1;
        return best[amount] == INF ? -1 : best[amount];
    }
}

function coinChange(coins, amount) {
  const INF = amount + 1;                 // a value no real answer can reach
  const best = new Array(amount + 1).fill(INF);
  best[0] = 0;
  for (let a = 1; a <= amount; a++) {
    for (const c of coins) {
      if (c <= a && best[a - c] + 1 < best[a]) best[a] = best[a - c] + 1;
    }
  }
  return best[amount] === INF ? -1 : best[amount];
}

fn solve(coins: &[usize], amount: usize) -> i64 {
    let inf = amount + 1;                        // never a real answer
    let mut best = vec![inf; amount + 1];
    best[0] = 0;
    for a in 1..=amount {
        for &c in coins {
            if c <= a && best[a - c] + 1 < best[a] {
                best[a] = best[a - c] + 1;
            }
        }
    }
    if best[amount] == inf { -1 } else { best[amount] as i64 }
}

import Data.Array

-- A lazy array is the idiomatic table: each entry refers to earlier entries.
solve :: [Int] -> Int -> Int
solve coins amount = if best ! amount == inf then -1 else best ! amount
  where
    inf  = amount + 1
    best = listArray (0, amount) [f a | a <- [0 .. amount]]
    f 0 = 0
    f a = minimum (inf : [best ! (a - c) + 1 | c <- coins, c <= a, best ! (a - c) < inf])