An Interest In:
Web News this Week
- March 21, 2024
- March 20, 2024
- March 19, 2024
- March 18, 2024
- March 17, 2024
- March 16, 2024
- March 15, 2024
May 17, 2022 10:19 am GMT
Original Link: https://dev.to/nantipatsoften/coin-change-problem-4fa3
Coin change problem
https://www.cs.usfca.edu/~galles/visualization/DPChange.html
const coin_change_bottom_up = (coins, sum) => { let memo = new Array(sum + 1).fill(Infinity); memo[0] = 0; for (let i = 1; i <= sum; i++) { for (let coin = 0; coin < coins.length; coin++) { if (coins[coin] <= i) { memo[i] = Math.min(memo[i], 1 + memo[i - coins[coin]]); } } } return memo[sum]; // O(n*m)};let coins = [1, 5, 10, 25];let sum = 18;console.log(coin_change_bottom_up(coins, sum));//---------------------------------const coin_change_top_dowm = (coins, sum, memo) => { if (sum == 0) return 0; if (sum < 0) return 1e9; // 1e9 = 1,000,000,000 // already solved cases: let ans = Infinity; for (let coin = 0; coin < coins.length; coin++) { if (coins[coin] <= sum) { let sub_ans = 1 + coin_change_top_dowm(coins, sum - coins[coin], memo); // console.log(sub_ans); ans = Math.min(ans, sub_ans); } } memo[sum] = ans; return memo[sum];};let memo = new Array(sum + 1).fill(Infinity);console.log(coin_change_top_dowm(coins, sum, memo));
Original Link: https://dev.to/nantipatsoften/coin-change-problem-4fa3
Share this article:
Tweet
View Full Article
Dev To
An online community for sharing and discovering great ideas, having debates, and making friendsMore About this Source Visit Dev To