Dynamic Programming Patterns to Ace Interviews

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)

Grid Traveller

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)

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)

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

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²)

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

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²)

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)

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store