Dynamic Programming Patterns to Ace Interviews

9 min readDec 15, 2021

Following materials are taken from freecodeCamp.org Youtube video course https://www.youtube.com/watch?v=oBt53YbR9Kk strongly recommend to watch the video!

Python version Colab Notebook @ https://colab.research.google.com/gist/Mageswaran1989/658eb75fed28f5953ac5167b3a14ff6d/dynamicprogramming.ipynb

Online Visualisation Tools:

https://visualgo.net/en/recursion

Dynamic Programming is useful when a problem as repetitive computation that can be cached. When cached the repetitive computation is inferred from the memory and thus reduces overall time taken to compute the solution.

Recursion Memoization

Visualise the problem as a tree
Implement the tree using recursion
Test it
Add memo object
Add a base case to return memo values

Array Tabulation

TODO for later time :)

Once the underlying patterns in DP problems is recognised, with practice its easy to get a hang of them.

Types:

Return one final value
Decision Problem (True/False)
Find a combination that matches given requirements
Finding a optimised solution in the combination

Tricks:

Remember the base case return type and final return should be the same
When one of the inputs happened to be list of values, then there is gonna be a for...loopin the recursion
When for...loop is involved, visualise what happens the last leaf nodes and build the result backwards

1One final value

Find a final result value for a given problem which can have repetitive intermediate computation.

Fibonacci Sequence

Base cases:
n < 0: Return n
fib(n) : fib(n-1) + fib(n-2)

Runtime: O(2^n)
Space: O(n)

def fib(n, memo = {}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    else:
        # calculate for first time
        memo[n] = fib(n-1, memo) + fib(n-2, memo)
        return memo[n]

Runtime: O(n)
Space: O(n)

Find a final result value for a given problem with multiple inputs, again which can have repetitive intermediate computations.

Grid Traveller

Say that you are a traveller on a grid. You begin in the top-left corner and your goal is to travel to the bottom-right corner. You may only move down or right. In how many ways can you travel to the goal on a grid with dimension m * n?

Write a function grid_traveller(m, n) that calculates this.

Base cases:
m or n ≤ 0 : When there is no cell to move return 0
m and n = 1 : When there is only one cell return 1
memo(m,n) = memo(m-1, n) + memo(m, n-1)

Time: O(2^n+m)
Space: O(n+m)

def grid_travel(m,n, memo={}):
    """

    :param m: Total number of rows
    :param n: Total number of columns
    :return:
    """
        # make the key with m & n, to differentiate rows and cols
    key = f"m{m}n{n}"    if key in memo:
        return memo[key]

    if (m == 1 and n==1):
        return 1
    elif (m ==0 or n ==0):
        return 0
    else:
        memo[key] = grid_travel(m-1, n, memo) + grid_travel(m, n-1, memo)
        return memo[key]

Time: O(n * m)
Space: O(n+m)

2 Decision Problem

Return a true or false after exploring all possible solution space

canSum

Write a function canSum(target_sum, numbers) that takes in a target sum and an array of numbers as arguments.

The function should return a boolean indicating whether or not it is possible to generate the target sum using numbers from the array.

You may use an element of the array as many times as needed and al inputs are non negative

m = target sum , n = array length
Time: O(n^m)
Space: O(m)

def can_sum(target_sum, values, memo={}):
    """:param target_sum:
    :param values: list
    :return:
    """
    # print(memo, values)
    if target_sum in memo:
        return memo[target_sum]    if target_sum == 0:
        return True
    if target_sum < 0:
        return False    for value in values:
        reminder = target_sum - value
        if can_sum(reminder, values, memo):
            memo[target_sum] = True
            return True     # If no way leads to zero then there is no possible values leads to sum
    memo[target_sum] = False
    return False

m = target sum , n = array length
Time: O(n*m) branch for every choice of number in the list of length n
Space: O(m)

Can Construct

Write function can_construct(target, word_bank) that accepts a target string and an array of strings

The function should return a boolean indicating whether or not the target can be constructed by concatenating elements of the word_bank array.

You may reuse elements of word_bank as many times as needed

m = target word length , n = word bank length
Time: O(n^m * m) n branches for each element in the list and m subtract operation in each branch and m operation to slice array
Space: O(m*m) m for stack depth and m for to store sliced array

def can_construct(target, word_bank, memo={}):   if target in memo:
        return memo[target]   if target == '':
        return True # When we found a way reconstruct the string   # Return true if any of branch returns true
    for word in word_bank:
        # check for matching prefix
        if target.startswith(word):
            suffix = target[len(word):]
            if can_construct(suffix, word_bank):
                memo[suffix] = True
                return True    # If no branch leads to positive case, return false
    memo[target] = False
    return False

m = target word length , n = word bank length
Time: O(n * m * m) n branches for each element in the list and m subtract operation in each branch and m operation to slice array
Space: O(m*m) m for stack depth and m for to store sliced array

3 Combination Problem

Find possible combination for given target and list of possible values.

How Sum

Write a function how_much(target_sum, numbers), that takes in a target_sum and an array of numbers as arguments.

The function should return an array containing any combination of elements that add up to exactly the target sum. If there is no combination that adds up to the target sum, return null.

If there are multiple combinations possible, you may return any single one.

m = target sum , n = array length
Time: O(n^m * m) n branches for each element in the list and m subtract operation in each branch and m operation to copy the array into result array
Space: O(m)


def how_sum(target_sum, values, memo={}):
    if target_sum in memo:
        return memo[target_sum]    if target_sum == 0:
        return []
    if target_sum < 0:
        return None    for value in values:
        ret = how_sum(target_sum - value, values, memo)
        if ret is not None:
            ret.append(value)
            memo[target_sum] = ret
            return ret    memo[target_sum] = None
    return None

m = target sum , n = array length
Time: O(n*m²)
Space: O(m²)

Count Construct

Write a function count_construct(target, word_bank) taht accepts a target string and an array of strings.

The function should return the number of ways that the target can be constructed by concatenating elements of the word_bank array.

You may reuse elements of word_bank as many time as needed.

m = target word length , n = word bank length
Time: O(n^m * m) n branches for each element in the list and m subtract operation in each branch and m operation to slice array
Space: O(m*m) m for stack depth and m for to store sliced array

def count_contruct(target, word_bank, memo={}):  if target in memo:
    return memo[target]  if len(target) == 0 :
    return True  total_ways = 0
  for word in word_bank:
    if target.startswith(word):
      suffix = target[len(word):]
      total_ways += count_contruct(suffix, word_bank)
      
  memo[target] = total_ways
  return total_ways

m = target word length , n = word bank length
Time: O(n * m * m) n branches for each element in the list and m subtract operation in each branch and m operation to slice array
Space: O(m*m) m for stack depth and m for to store sliced array

4 Optimisation Problem

Find all possible combination for given target and list of possible values and return the best one

Best Sum

Write a function best_sum(target_sum, numbers) that takes in a target sum and an array of numbers as arguments.

The function should return an array containing the shortest combination of numbers that add up to exactly the target sum.

If there is a tie for the shortest combination, you may return any on of the shortest

m = target sum , n = array length
Time: O(n^m * m) n branches for each element in the list and m subtract operation in each branch and m operation to copy the array into result array
Space: O(m²)

def best_sum(target_sum, values, memo):  if target_sum in memo:
        return memo[target_sum]  if target_sum == 0:
        return []  if target_sum < 0:
        return None  best_pair = None  for value in values:
        ret = best_sum(target_sum=target_sum - value, values=values, memo=memo)
        if ret is not None:
            res = ret + [value]
            if best_pair is None or len(res) < len(best_pair):
                best_pair = res
                memo[target_sum] = best_pair
                # return best_pair # Dont return the value until all possible combinations are evaluated for child tree  memo[target_sum] = best_pair
    return memo[target_sum]

m = target sum , n = array length
Time: O(n*m²)
Space: O(m²)

All Construct

Write a function all_construct(target, word_bank) that accepts a target string and an array of strings

The function should return a 2D array containing all of the ways that the target can be constructed by concatenating elements of the word bank array. Each element of the 2D array should represent one combination that constructs the target.

You may reuse elements of the word bank as many times as needed.

def all_construct(target, word_bank, memo={}):    if target in memo:
        return memo[target]    if target in memo:
        return memo[target]    if target == '':
        return [[]]    res = []
    for word in word_bank:
        if target.startswith(word):
            suffix = target[len(word):]
            suffix_ways = all_construct(suffix, word_bank)
            target_ways = list(map(lambda l: l + [word], suffix_ways))
            res.extend(target_ways)     memo[target] = res     return res

m = target word length , n = number of words in word bank length
Time: O(n^m ) If complexity is exponential i.e m^n then we can ignore additional complexity like slicing the array
Space: O(m)