You are viewing a single comment's thread. Return to all comments →
A recrursive solution in python using memoization(dp)/ bottom up approach. Passes all the test cases.
coin_array = [1,2,5,10,20,50,100,200] mat = [[-1 for i in range(9)] for i in range(100000+1) ] def ways(coin_array,sum,n): if mat[sum][n]!=-1: return mat[sum][n] if n==1: return 1 if coin_array[n-1] > sum: return ways(coin_array, sum, n-1) if sum==1: mat[sum][n] = 1 return 1 if sum==2: mat[sum][n] = 2 return 2 else: x = ways(coin_array,sum -coin_array[n-1], n) + ways(coin_array, sum, n-1) mat[sum][n] = x return x t = int(input()) for a0 in range(t): c = int(input()) print(ways(coin_array,c,8)%(1000000000+7))
print(ways(coin_array,c,8)%(1000000000+7))
Seems like cookies are disabled on this browser, please enable them to open this website
Project Euler #31: Coin sums
You are viewing a single comment's thread. Return to all comments →
A recrursive solution in python using memoization(dp)/ bottom up approach. Passes all the test cases.