# π€ leetcode 322. Coin Change | medium | dynamic-programming | javascript

One of the famous dynamic programming problems.

## ποΈ Problems

322. Coin Change - LeetCode

``````You are given an integer array coins representing coins of different denominations
and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount.
If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.
``````
``````Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1
``````

## π€ Understand problem

• Given the amount of money, find a minimum number of coins to make up that amount.

## π₯³ Think differently

• Need to check all possible cases.
• Just use coins to make up that amount.

## β¬οΈ bottom-up : [object Object] array

• `dp[amount]` : the minimum number of coins with that amount of money
``````const dp = Array(amount + 1).fill(Infinity);
dp[0] = 0;
``````

#### π₯³β¬οΈ Think differently

• If you know `dp[i - coin]` (the minimum number of coins with `i-coin` amount)
• What is `dp[i]` ?
• I used one more coin of the minimum coin usage of `i-coin` amount `dp[i-coin]`.
• `dp[i] = dp[i-coin] + 1`
• `dp[i]` is the minimum number of all cases
• `Math.min(dp[i], dp[i-coin] + 1)`

#### π₯β¬οΈ My solution

``````var coinChange = function (coins, amount) {
const dp = Array(amount + 1).fill(Infinity);
dp[0] = 0;

for (let i = 1; i <= amount; i += 1) {
for (const coin of coins) {
if (i - coin < 0) continue;

dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
}
}

return dp[amount] === Infinity ? -1 : dp[amount];
};
``````

## β¬οΈ top-down : [object Object]

#### π₯³β¬οΈ Think differently

• `dp(money)` : the minimum number of coins to make up `money`.
• When not possible, return `-1`.
• When possible, it should use one more coin of the previous result: `dp(money-coin)` + 1.

#### β¬οΈ top-down without memoization

``````var coinChange = function (coins, amount) {
const dp = (remain) => {
if (remain < 0) return -1;
if (remain === 0) return 0;

let min = Infinity;
for (const coin of coins) {
if (remain - coin < 0) continue;

const res = dp(remain - coin);
if (res === -1) continue;
min = Math.min(min, 1 + res);
}
return min === Infinity ? -1 : min;
};

return dp(amount);
};
``````

#### π₯β¬οΈ top-down: My Solution

``````/**
* @param {number[]} coins
* @param {number} amount
* @return {number}
*/
var coinChange = function (coins, amount) {
const cache = {};

const dp = (remain) => {
if (remain < 0) return -1;
if (remain === 0) return 0;
if (cache[remain] !== undefined) return cache[remain];

let min = Infinity;
for (const coin of coins) {
if (remain - coin < 0) continue;

const res = dp(remain - coin);
if (res === -1) continue;
min = Math.min(min, 1 + res);
}
return (cache[remain] = min === Infinity ? -1 : min);
};

return dp(amount);
};
``````