FilesExpand file tree

 patch-2

/

coin_change.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

26 lines (22 loc) · 825 Bytes

 patch-2

/

coin_change.py

Copy path

Top

File metadata and controls

• Code
• Blame

26 lines (22 loc) · 825 Bytes

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

"""

You have m types of coins available in infinite quantities

where the value of each coins is given in the array S=[S0,... Sm-1]

Can you determine number of ways of making change for n units using

the given types of coins?

https://www.hackerrank.com/challenges/coin-change/problem

"""

from __future__ import print_function

def dp_count(S, m, n):

table = [0] * (n + 1)

# Base case (If given value is 0)

table[0] = 1

# Pick all coins one by one and update table[] values

# after the index greater than or equal to the value of the

# picked coin

for i in range(0, m):

for j in range(S[i], n + 1):

table[j] += table[j - S[i]]

return table[n]

if __name__ == '__main__':

print(dp_count([1, 2, 3], 3, 4)) # answer 4

print(dp_count([2, 5, 3, 6], 4, 10)) # answer 5