javascript-data-structures-and-algorithms/src/dynamic-programming/2d/coin-change-ii/coinChange.js at master · evgenirusev/javascript-data-structures-and-algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
/**
 * https://leetcode.com/problems/coin-change-ii
 * @param {number} amount
 * @param {number[]} coins
 * @return {number}
 * Bottom up DP
 * Time O(N * amount)
 * Space O(N)
 */
function coinChange(amount, coins) {
    const dp = new Array(amount + 1).fill(0);
    dp[0] = 1;

    for (let i = coins.length - 1; i >= 0; i--)
        for (let j = coins[i]; j <= amount; j++)
            dp[j] += dp[j - coins[i]];

    return dp[amount];
}

// Top down DP
// Time O(N * amount) | Space O(N * amount)
// function coinChange(amount, coins) {
//     const memo = Array.from({ length: coins.length }, () => Array(amount + 1).fill(undefined));

//     function dfs(i, a, cache) {
//         if (a === amount)
//             return 1;

//         if (a > amount)
//             return 0;

//         if (i === coins.length)
//             return 0;

//         if (cache[i][a] !== undefined)
//             return cache[i][a];

//         cache[i][a] = dfs(i    , a + coins[i], cache)
//                     + dfs(i + 1, a           , cache);

//         return cache[i][a];
//     }

//     var res = dfs(0, 0, memo);
//     return res;
// }

// Brute force backtracking - timeout
// var coinChange = function(amount, coins) {
//     let res = 0;
//     let sum = 0;

//     function dfs(i) {
//         if (i === coins.length || sum > amount)
//             return;

//         if (sum === amount) {
//             res++;
//             return;
//         }

//         for (let j = i; j < coins.length; j++) {
//             sum += coins[j];
//             dfs(j);
//             sum -= coins[j];
//         }
//     }

//     dfs(0);

//     return res;
// };

module.exports = coinChange;