diff options
author | Haidong Ji | 2018-12-17 21:36:34 -0600 |
---|---|---|
committer | Haidong Ji | 2018-12-17 21:36:34 -0600 |
commit | 42b954fb8365969c979c5cd1f3c1cd9ed1f7ffc9 (patch) | |
tree | 32472f1ee553f5822cb36dd1178c1b1fec1d06b4 /AlgoDesignAndTechniqueEdxPython/sources/coin_change_dynamic_programming.py | |
parent | 1d6a57ac37f0c56a7639c1124be5501f699f3027 (diff) |
Coin change Dynamic Programming done!
Diffstat (limited to 'AlgoDesignAndTechniqueEdxPython/sources/coin_change_dynamic_programming.py')
-rw-r--r-- | AlgoDesignAndTechniqueEdxPython/sources/coin_change_dynamic_programming.py | 20 |
1 files changed, 20 insertions, 0 deletions
diff --git a/AlgoDesignAndTechniqueEdxPython/sources/coin_change_dynamic_programming.py b/AlgoDesignAndTechniqueEdxPython/sources/coin_change_dynamic_programming.py new file mode 100644 index 0000000..f8aabd3 --- /dev/null +++ b/AlgoDesignAndTechniqueEdxPython/sources/coin_change_dynamic_programming.py @@ -0,0 +1,20 @@ +# Uses python3 +import sys + + +def getChange(money): + denominations = [1, 3, 4] + minNumCoins = [0] * (money + 1) + for m in range(1, len(minNumCoins)): + minNumCoins[m] = float('inf') + for i in range(len(denominations)): + if m >= denominations[i]: + numCoins = minNumCoins[m - denominations[i]] + 1 + if numCoins < minNumCoins[m]: + minNumCoins[m] = numCoins + return minNumCoins[money] + + +if __name__ == '__main__': + m = int(sys.stdin.read()) + print(getChange(m)) |