Coin Change (Minimum Coins)

/*
 * Problem : Fewest coins for an amount.
 * Input   : Coins array and the amount k.
 * Output  : The fewest coins or -1.
 * Approach: Build answers from small amounts.
 * Time    : O(k * n)
 * Space   : O(k)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    // This method solves the task. It receives the input and returns the answer.
    static int solve(int[] a, int k) {
        // Step 1: best[x] = the fewest coins for the amount x. Use a big number for "not possible yet".
        int impossible = 1000000000;
        int[] best = new int[k + 1];
        java.util.Arrays.fill(best, impossible);

        // Step 2: The amount 0 needs 0 coins.
        best[0] = 0;

        // Step 3: Fill the table from small amounts to large amounts.
        for (int amount = 1; amount <= k; amount++) {
            for (int coin : a) {
                // Step 4: Use this coin if it fits. Then we need one coin plus the best answer for the rest.
                if (coin <= amount && best[amount - coin] + 1 < best[amount]) {
                    best[amount] = best[amount - coin] + 1;
                }
            }
        }

        // Step 5: If the value is still the big number, the amount can not be made.
        return best[k] >= impossible ? -1 : best[k];
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int size = scanner.nextInt();
        int[] a = new int[size];
        for (int i = 0; i < size; i++) {
            a[i] = scanner.nextInt();
        }
        int k = scanner.nextInt();
        System.out.println(solve(a, k));
    }
}