forked from adityabisoi/ds-algo-solutions
-
Notifications
You must be signed in to change notification settings - Fork 0
/
solution.py
29 lines (23 loc) · 799 Bytes
/
solution.py
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
27
28
29
#Recursive solution for the intuition.
#Recursing through the possibilty of solution with nth coin and without nth coin.
#Bottom up DP to track overlapping subproblem solution.
N,M = list(map(int,input().strip().split(' ')))
coins = list(map(int,input().strip().split(' ')))
count = 0
def count_make_change_recursive(N, coins, M):
if N < 0:
return 0
if N == 0:
return 1
if M <= 0:
return 0
return count_make_change(N-coins[M-1], coins, M) + count_make_change(N,coins,M-1)
def count_make_change_bottom_up(N, coins, M):
counts = [0] * (N+1)
counts[0] = 1
for i in range(0, M):
sum = 0
for j in range(coins[i],N+1):
counts[j] += counts[j-coins[i]]
return counts[N]
print(count_make_change_bottom_up(N,coins,M))