/**
 * Brute Force - DFS
 * Time O(2^N) | Space O(N)
 * @param {number} amount
 * @param {number[]} coins
 * @return {number}
 */
 var change = (amount, coins, n = (coins.length)) => {
    const isBaseCase1 = (amount === 0);
    if (isBaseCase1) return 1;

    const isBaseCase2 = (n === 0);
    if (isBaseCase2) return 0;

    return dfs(amount, coins, n);/* Time O(2^N) | Space O(N) */
}

var dfs = (amount, coins, n) => {
    const isLess = (amount < coins[(n - 1)]);
    if (isLess) return change(amount, coins, (n - 1));       /* Time O(2^N) | Space O(N) */

    const left = change((amount - coins[(n - 1)]), coins, n);/* Time O(2^N) | Space O(N) */
    const right = change(amount, coins, (n - 1));            /* Time O(2^N) | Space O(N) */

    return (left + right);
}

/**
 * DP - Top Down
 * Matrix - Memoization
 * Time O(N * AMOUNT) | Space O(N * AMOUNT)
 * https://leetcode.com/problems/coin-change-ii/
 * @param {number} amount
 * @param {number[]} coins
 * @return {number}
 */
var change = (amount, coins, n = (coins.length), memo = initMemo(coins, amount)) => {
    const isBaseCase1 = (n === 0);
    if (isBaseCase1) return 0;

    const isBaseCase2 = (amount === 0);
    if (isBaseCase2) return 1;

    const hasSeen = (memo[n][amount] !== null);
    if (hasSeen) return memo[n][amount];

    return dfs(amount, coins, n, memo);/* Time O(N * AMOUNT) | Space O((N * AMOUNT) + HEIGHT) */
}

var initMemo = (coins, amount) => new Array(coins.length + 2).fill()
    .map(() => new Array(amount + 2).fill(null));

var dfs = (amount, coins, n, memo) => {
    const isLess = (amount < coins[(n - 1)]);
    if (isLess) {
        memo[n][amount] = change(amount, coins, (n - 1), memo);     /* Time O(N * AMOUNT) | Space O(HEIGHT) */
        return memo[n][amount];
    }

    const left = change((amount - coins[(n - 1)]), coins, n, memo);/* Time O(N * AMOUNT) | Space O(HEIGHT) */
    const right = change(amount, coins, (n - 1), memo);            /* Time O(N * AMOUNT) | Space O(HEIGHT) */

    memo[n][amount] = (left + right);                              /*                    | Space O(N * AMOUNT) */
    return memo[n][amount];
}

/**
 * DP - Bottom Up
 * Array - Tabulation
 * Time O(N * AMOUNT) | Space O(N * AMOUNT)
 * https://leetcode.com/problems/coin-change-ii/
 */
 var change = (amount, coins) => {
    const tabu = initTabu(amount, coins);/* Time O(N * AMOUNT) | Space O(N * AMOUNT) */

    search(amount, coins, tabu);         /* Time O(N * AMOUNT) | Space O(N * AMOUNT) */

    return tabu[coins.length][amount];
}

var initTabu = (amount, coins) => {
    const tabu = new Array((coins.length + 1)).fill()/* Time O(N) | Space O(N) */
        .map(() => new Array((amount + 1)).fill(0));     /* Time O(AMOUNT) | Space O(AMOUNT) */

    tabu[0][0] = 1;                                   /*          | Space O(N * AMOUNT) */

    return tabu;
}

var search = (amount, coins, tabu) => {
    for (let coin = 1; coin <= coins.length; coin++) {   /* Time O(N)*/
        tabu[coin][0] = 1;                                       /* Space O(N * AMOUNT) */

        for (let _amount = 1; _amount <= amount; _amount++) {/* Time O(AMOUNT) */
            tabu[coin][_amount] = tabu[coin - 1][_amount];

            const canUpdate = (0 <= (_amount - coins[(coin - 1)]));
            if (!canUpdate) continue;

            const val = tabu[coin][(_amount - coins[(coin - 1)])];
            tabu[coin][_amount] += val                           /* Space O(N * AMOUNT) */
        }
    }
}

/**
 * DP - Bottom Up
 * Array - Tabulation
 * Time O(N * AMOUNT) | Space O(AMOUNT)
 * https://leetcode.com/problems/coin-change-ii/
 * @param {number} amount
 * @param {number[]} coins
 * @return {number}
 */
var change = (amount, coins) => {
    const tabu = initTabu(amount);

    search(amount, coins, tabu);

    return tabu[amount];
};

var initTabu = (amount) => {
    var tabu = new Array((amount + 1)).fill(0);

    tabu[0] = 1;

    return tabu;
}

var search = (amount, coins, tabu) => {
    for (const coin of coins) {
        for (let _amount = 0; (_amount < (amount + 1)); _amount++) {
            const canUpdate = (coin <= _amount);
            if (!canUpdate) continue;

            tabu[_amount] += tabu[(_amount - coin)];
        }
    }
}