Grokking Dynamic Programming Patterns for Coding Interviews

0% completed

​

Number factors

Problem Statement

Given a number 'n', implement a method to count how many possible ways there are to express 'n' as the sum of 1, 3, or 4.

Example 1:

n : 4
Number of ways = 4
Explanation: Following are the four ways we can express 'n' : {1,1,1,1}, {1,3}, {3,1}, {4}

Example 2:

n : 5
Number of ways = 6
Explanation: Following are the six ways we can express 'n' : {1,1,1,1,1}, {1,1,3}, {1,3,1}, {3,1,1}, 
{1,4}, {4,1}

Let's first start with a recursive brute-force solution.

Try it yourself

Try solving this question here:

.....

.....

.....

Like the course? Get enrolled and start learning!
Mohammed Dh Abbas

Mohammed Dh Abbas

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

Shan

· 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:

M

mailman14736

· a month ago

Why is 1 the expected answer for input 0 ??? You cannot express 0 as the sum of 1, 3, 4 ?

This is basically the same problem as the previous 2 BTW - this section felt a bit lazy compared to the 0/1 Knapsack DP section.

Show 1 reply