We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. The Coin Change Problem
  5. Discussions

The Coin Change Problem

  • Dularish
     + 1 comment

    Can't seem to figure out the problem. It gives correct output on running in my IDE.

    #!/bin/python3

import math
import os
import random
import re
import sys

# Complete the getWays function below.
memoizing_dict = {}

# Complete the getWays function below.
def getWays(n, c):
    global memoizing_dict
    if n < 0:
        return 0
    elif n == 0:
        return 1
    elif (n,len(c)) in memoizing_dict.keys():
        return memoizing_dict[(n,len(c))]
    else:
        cum_sum = 0
        for c_index in range(len(c)):
            c_item = c[c_index]
            if c_item > n:
                continue
            else:
                result = getWays(n-c_item, c[c_index:])
                if result > 0:
                    cum_sum += result
        memoizing_dict[(n,len(c))] = cum_sum
        return cum_sum
    

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    nm = input().split()

    n = int(nm[0])

    m = int(nm[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)
    print(ways)
    fptr.close()