/*
Runtime: 9 ms, faster than 84.83% of Java online submissions for Coin Change.
Memory Usage: 35.8 MB, less than 97.63% of Java online submissions for Coin Change.
*/
class Solution {
    public int coinChange(int[] coins, int amount) {
        if (coins.length == 0 ) return amount > 0 ? -1: 0;
        if (amount == 0) return 0;

        int[] cache = new int[amount + 1];

        cache[0] = 0;

        for (int k = 0; k <= amount; k++) {
            if (cache[k] <= 0 && k > 0) continue;

            for (int i = 0; i < coins.length; i++) {
                int next = k + coins[i];
                if (next <= amount && next > 0) {
                    int count = cache[k] + 1;

                    if (cache[next] <= 0 || cache[next] > count) {
                        cache[next] = count;
                    }
                }
            }
        }

        return cache[amount] > 0 ? cache[amount]: -1;
    }
}