Grokking LinkedIn Coding Interview

0% completed

​
Hidden Document
Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content

.....

.....

.....

Like the course? Get enrolled and start learning!
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, {})