Created
December 31, 2016 18:01
-
-
Save Muzietto/a67e7a4f8fc6065c65c63991db0aea1f to your computer and use it in GitHub Desktop.
Dynamic programming self-tuition - minimal number of coins needed to reach a given total amount (BETTER SOLUTION)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| function betterMinNumOfCoins(coinages, amount) { | |
| // sort coinages | |
| coinages = coinages.sort((a,b)=>a-b); | |
| var minCoinage = Math.min.apply(null, coinages); | |
| var dp = new Array(amount + 1).fill(Infinity); | |
| dp[0] = 0; | |
| for (var i = 1; i <= amount; i++) { | |
| for (var j = 0; j < coinages.length; j++) { | |
| var coinage = coinages[j]; | |
| if (coinage > i) break; | |
| if (dp[i - coinage] + 1 < dp[i]) { | |
| if (dp[i] === Infinity) dp[i] = 0; | |
| dp[i] = dp[i - coinage] + 1; | |
| } | |
| } | |
| } | |
| return dp[amount - 1]; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
This one comes from https://www.topcoder.com/community/data-science/data-science-tutorials/dynamic-programming-from-novice-to-advanced/ and it is a lot more conscious and coherent.
It is based on a state matrix dp and it bears most probably more learning potential.