class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;

        for (int coin: coins)
            for (int n = coin; n <= amount; n++)
                dp[n] += dp[n - coin];

        return dp[amount];
    }
}

class Solution {
    public int change(int amount, int[] coins) {
        return change(amount, coins.length - 1, coins, new int[coins.length][amount + 1]);
    }

    private int change(int amount, int k, int[] coins, int[][] cache) {
        if (amount == 0)  return 1;
        if (k == -1) return 0;

        if (cache[k][amount] != 0) return cache[k][amount] - 1;

        int result = change(amount, k - 1, coins, cache);
        if (amount >= coins[k]) {
            result += change(amount - coins[k], k, coins, cache);
        }

        cache[k][amount] = result + 1;
        return result;
    }
}