Grokking Dynamic Programming Patterns for Coding Interviews
Vote

0% completed

​

Coin Change

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Anonymous

· 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, {})
A

Anonymous

· 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

Reading Progress

0%

Vote for new content