title: How many ways to get the change?
body: <p>While practicing the following dynamic programming question on HackerRank, I got the 'timeout' error. The code run successfully on some test examples, but got 'timeout' errors on others. I'm wondering how can I further improve the code.</p>
  <p>The question is</p>
  <pre><code>Given an amount and the denominations of coins available, determine how many ways change can be made for amount. There is a limitless supply of each coin type.
  Example:
  n = 3
  c = [8, 3, 1, 2]
  
  
  There are 3 ways to make change for n=3 : {1, 1, 1}, {1, 2}, and {3}. 
  </code></pre>
  <p>My current code is</p>
  <pre><code>import math
  import os
  import random
  import re
  import sys
  
  from functools import lru_cache
  
  #
  # Complete the 'getWays' function below.
  #
  # The function is expected to return a LONG_INTEGER.
  # The function accepts following parameters:
  #  1. INTEGER n
  #  2. LONG_INTEGER_ARRAY c
  #
  
  def getWays(n, c):
      # Write your code here
      #c = sorted(c)
      
      @lru_cache
      def get_ways_recursive(n, cur_idx):
          cur_denom = c[cur_idx]
          n_ways = 0        
          if n == 0: 
              return 1
          if cur_idx == 0:
              return 1 if n % cur_denom == 0 else 0
          
          for k in range(n // cur_denom + 1):
              n_ways += get_ways_recursive(n - k * cur_denom, 
                     cur_idx - 1)
          return n_ways
      
      return get_ways_recursive(n, len(c) - 1)
     
  
  if __name__ == '__main__':
      fptr = open(os.environ['OUTPUT_PATH'], 'w')
  
      first_multiple_input = input().rstrip().split()
  
      n = int(first_multiple_input[0])
  
      m = int(first_multiple_input[1])
  
      c = list(map(int, input().rstrip().split()))
  
      # Print the number of ways of making change for 'n' units using coins having the values given by 'c'
  
      ways = getWays(n, c)
  
      fptr.write(str(ways) + '\n')
  
      fptr.close()
  </code></pre>
  <p>It timed out on the following test example</p>
  <pre><code>166 23 # 23 is the number of coins below.
  5 37 8 39 33 17 22 32 13 7 10 35 40 2 43 49 46 19 41 1 12 11 28
  </code></pre>