Grokking Dynamic Programming Patterns for Coding Interviews
Vote

0% completed

​

Solution: Coin Change

Introduction

Given an infinite supply of ‘n’ coin denominations and a total money amount, we are asked to find the total number of distinct ways to make up that amount.

Example:

Denominations: {1,2,3}
Total amount: 5
Output: 5
Explanation: There are five ways to make the change for '5', here are those ways:
  1. {1,1,1,1,1} 
  2. {1,1,1,2} 
  3. {1,2,2}
  4. {1,1,3}
  5. {2,3}

.....

.....

.....

Like the course? Get enrolled and start learning!
G

Gary

· 4 years ago

Why is this check done in the recursive helper function instead of in the count_change function? denominations list never changes, right?

n = len(denominations) if n == 0

Show 2 replies
Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

class Solution:
  def countChange(self, denominations, total):
    
    def dp(index, acc, memo):
      if (index, acc) in memo:
        return memo[(index, acc)]

      if acc == total:
        return 1

      if acc > total or index == len(denominations):
        return 0

      with_item = dp(index, acc + denominations[index], memo) 
      without_item = dp(index + 1, acc, memo)

      result = with_item + without_item
      memo[(index, acc)] = result

      return result
    
    return dp(0, 0, {})
Online Courses

Online Courses

· 4 months ago

class Solution:
  def countChange_memo(self, denominations, total):
    n = len(denominations)

    memo = {}

    def change(idx, current_sum):
      print(idx, current_sum)
      if current_sum == total:
        return 1
      if idx == n or current_sum > total:
        return 0
      
      key = (idx, current_sum)
      if key in memo:
        return memo[key]

      count = change(idx + 1, current_sum)
      count += change(idx, current_sum + denominations[idx])

      memo[key] = count

      return count

    return change(0, 0)

  def countChange_2d_dp(self, denominations, total):
    n = len(denominations)

    # state
    dp =[[0] * (total + 1) for _ in range(n + 1)]

    # base case
    for i in range(n + 1):
      dp[i][total] = 1

    # recursion relation
    for