Hackerrank - Dynamic Programming - The Coin Change Problem

You have  types of coins available in infinite quantities where the value of each coin is given in the array . Can you determine the number of ways of making change for  units using the given types of coins? For example, if , and , we can make change for  units in three ways: , , and .

Given , , and , print the number of ways to make change for  units using any number of coins having the values given in .






Input Format




The first line contains two space-separated integers describing the respective values of  and . 
The second line contains  space-separated integers describing the respective values of  (the list of distinct coins available in infinite amounts).






Constraints







Each  is guaranteed to be distinct.


Hints

Solve overlapping subproblems using Dynamic Programming (DP): 
You can solve this problem recursively but will not pass all the test cases without optimizing to eliminate the overlapping subproblems. Think of a way to store and reference previously computed solutions to avoid solving the same subproblem multiple times.
Consider the degenerate cases: 

How many ways can you make change for  cents?
How many ways can you make change for  cents if you have no coins?


If you're having trouble defining your solutions store, then think about it in terms of the base case .
The answer may be larger than a -bit integer.







Output Format




Print a long integer denoting the number of ways we can get a sum of  from the given infinite supply of  types of coins.






Sample Input 0




4 3
1 2 3








Sample Output 0




4








Explanation 0




There are four ways to make change for  using coins with values given by :







Thus, we print  as our answer.






Sample Input 1




10 4
2 5 3 6








Sample Output 1




5








Explanation 1




There are five ways to make change for  units using coins with values given by :








Thus, we print  as our answer.

#!/bin/python

import sys

def getWays(n, c):
 arr = [0 for h in range(n+1)]
 arr[0] = 1

 for k in c:
  for i in range(1,n+1):
   if n>=k:
    if i>=k:
     arr[i] += arr[i-k]
 return arr

 # Complete this function

n, m = raw_input().strip().split(' ')
n, m = [int(n), int(m)]
c = map(long, raw_input().strip().split(' '))
# Print the number of ways of making change for 'n' units using coins having the values given by 'c'
ways = getWays(n, c)
print ways[-1]