Grokking Dynamic Programming Patterns for Coding Interviews
Vote

0% completed

​

Solution: Number factors

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Anonymous

· 2 years ago

class Solution:
  def countWays(self, n):
    
    def dp(acc, memo):
      if acc in memo:
        return memo[acc]
      if acc == n:
        return 1 
      if acc > n:
        return 0
      
      result = dp(acc + 1, memo) + dp(acc + 3, memo) + dp(acc + 4, memo)
      memo[acc] = result
      
      return result

    return dp(0, {})
A

Anonymous

· 4 years ago

The following text is a typo and should instead be CountWays(6) to match the image it is referring to.

Let’s visually draw the recursion for CountWays(5) to see the overlapping subproblems:

Reading Progress

0%

Vote for new content