The best course on Dynamic Programming happened to be in JavaScript. Because Python has some particularities in how it handles data structures and organises stack frames, here is a Python version of the functions explained in the course.
The structure of this post mirrors the course video, with all relevant links with timestamps included. First, there is a brute force solution for the stated problem and then an improved memoized version. I use the original function names in sub-headers for easy reference. However, in description and code, I stick to Python conventions for naming and implementation as much as possible.
Quick reference
- Fibonacci problem
- Grid traveller problem
- canSum problem
- howSum problem
- bestSum problem
- canConstruct problem
- countConstruct problem
- allConstruct problem
- fib tabulation
- Grid traveller tabulation
- canSum tabulation
- howSum tabulation
- bestSum tabulation
- canConstruct tabulation
- countConstruct tabulation
- allConstruct tabulation
Fibonacci problem. Memoization
Problem: write a function fib(n) that takes in a number as an argument. The function should return the n-th number of the Fibonacci sequence. The 0th number of the sequence is 0. The 1st number of the sequence is 1. To generate the next number of the sequence, we sum the previous two.
Fibonacci explanation in the course. And corresponding Python code:
# O(2**n)
def fib(n: int) -> int:
if n <= 2:
return 1
else:
return fib(n-1)+fib(n-2)
Python implementation notes for memoized solution. Note this empty dict memo object in function parameters. Usually, mutable types as defaults in function parameters is a bad idea. This is because when Python loads function into memory, it assigns a pointer to this object (in this case, memo dictionary). So it is always the same dictionary, as it points to the same location in memory. And it will aggregate values across all function calls. In some cases, this can be undesirable, but in the case of memoizing Fibonacci numbers, this is useful, so we can initiate an empty dictionary as a memo object. Another worth mentioning point is that we do not need to pass memo object in subsequent recursive calls, as it is already in the stack.
# memoization O(n)
def fib(n: int, memo={}) -> int:
if n in memo.keys():
return memo[n]
if n <= 2:
return 1
else:
memo[n] = fib(n-1)+fib(n-2)
return memo[n]
print(fib(6)) # 8
print(fib(7)) # 13
print(fib(8)) # 21
print(fib(50)) # 12586269025
Grid traveller problem
Problem: Say that you are a traveller on a 2D grid. You begin in the top-left corner and your goal is to travel to the bottom-right corner. You only move down or right.
In how many ways can you travel to the goal on a grid with dimensions m * n?
Grid traveller problem explanation and Python implementation:
# O(2**(m+n))
def grid_traveller(m: int, n: int) -> int:
if m == 1 and n == 1:
return 1
if m == 0 or n == 0:
return 0
return grid_traveller(m - 1, n) + grid_traveller(m, n - 1)
Python implementation note for memoized solution. In Python concatenating string and integer will result in “TypeError: unsupported operand type(s) for +: ‘int’ and ‘str'”. To avoid this we cast integer into string using syntax str(int)
# memoized O(m*n)
def grid_traveller(m: int, n: int, memo={}) -> int:
key = str(m) + "," + str(n)
if key in memo.keys():
return memo[key]
if m == 1 and n == 1:
return 1
if m == 0 or n == 0:
return 0
memo[key] = grid_traveller(m - 1, n) + grid_traveller(m, n - 1)
return memo[key]
print(grid_traveller(1, 1)) # 1
print(grid_traveller(2, 3)) # 3
print(grid_traveller(3, 2)) # 3
print(grid_traveller(3, 3)) # 6
print(grid_traveller(18, 18)) # 2333606220
canSum problem
Problem: write a function can_sum(target_sum, numbers) that takes in a target_sum and a list 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 list. You may use an element of the list as many times as needed. You may assume that all input numbers are nonnegative.
canSum problem explanation and Python code:
# O(n**m)
def can_sum(target_sum: int, numbers: list) -> bool:
if target_sum == 0:
return True
if target_sum < 0:
return False
for num in numbers:
remainder = target_sum - num
if can_sum(remainder, numbers):
return True
return False
Python implementation notes for memoized solution. Keeping in mind how Python treats mutable defaults in function parameters, it is clear that we cannot use an empty dictionary as the default parameter for the memo object in this version of the problem. As all inputs will be different, so different will be the ways to reach target_sum. For this program to work, we need to pass an empty memo dictionary for each function call. Thus the memo dictionary will be constructed individually for given parameters and will not be shared across calls.
# memoized O(m*n)
def can_sum(target_sum: int, numbers: list, memo) -> bool:
if target_sum in memo.keys():
return memo[target_sum]
if target_sum == 0:
return True
if target_sum < 0:
return False
for num in numbers:
remainder = target_sum - num
if can_sum(remainder, numbers, memo):
memo[target_sum] = True
return memo[target_sum]
memo[target_sum] = False
return memo[target_sum]
print(can_sum(7, [2, 3], memo={})) # True
print(can_sum(7, [5, 3, 4, 7], memo={})) # True
print(can_sum(7, [2, 4], memo={})) # False
print(can_sum(8, [2, 3, 5], memo={})) # True
print(can_sum(300, [7, 14], memo={})) # False
howSum problem
Problem: write a function how_sum(target_sum, numbers) that takes in a target_sum and a list of numbers as arguments. The function should return a list 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, then return None. If there are multiple combinations possible, you may return any single one. You may use an element of the list as many times as needed. You may assume that all input numbers are nonnegative.
howSum problem explanation and Python code:
# O((n**m)*m)
def how_sum(target_sum: int, numbers: list) -> list:
if target_sum == 0:
return []
if target_sum < 0:
return None
for num in numbers:
remainder = target_sum - num
remainder_res = how_sum(remainder, numbers)
if remainder_res is not None:
remainder_res.append(num)
return remainder_res
return None
Python implementation notes for memoized solution. As with can_sum() problem, we cannot pass empty dictionary as default parameter for memo object. It should be defined separately for each function call.
# memoized O((m**2)*n)
def how_sum(target_sum: int, numbers: list, memo: dict) -> list:
if target_sum in memo.keys():
return memo[target_sum]
if target_sum == 0:
return []
if target_sum < 0:
return None
for i in numbers:
remainder = target_sum - i
remainder_res = how_sum(remainder, numbers, memo)
if remainder_res is not None:
remainder_res.append(i)
memo[target_sum] = remainder_res
return memo[target_sum]
memo[target_sum] = None
print(how_sum(7, [2, 3], memo={})) # [3, 2, 2]
print(how_sum(7, [5, 3, 4, 7], memo={})) # [4, 3]
print(how_sum(7, [2, 4], memo={})) # None
print(how_sum(8, [2, 3, 5], memo={})) # [2, 2, 2, 2]
print(how_sum(300, [7, 14], memo={})) # None
bestSum problem
Problem: write a function best_sum(target_sum, numbers) that takes in a target_sum and a list of numbers as arguments. The function should return a list containing the shortest combination of numbers that add up to exactly the target_sum.
If there a tie for the shortest combination, you may return any one of the shortest.
Python code for the bestSum problem:
# O((n**m)*m)
def best_sum(target_sum: int, numbers: list) -> list:
if target_sum == 0:
return []
if target_sum < 0:
return None
shortest_combination = None
for num in numbers:
remainder = target_sum - num
remainder_combination = best_sum(remainder, numbers)
if remainder_combination is not None:
remainder_combination.append(num)
combination = remainder_combination
if (shortest_combination is None) or (len(combination) < len(shortest_combination)):
shortest_combination = combination
return shortest_combination
Python implementation notes for memoized solution. In this problem we need to explicitly create a copy of the remainder combination variable.
# memoized O((m**2)*n)
def best_sum(target_sum: int, numbers: list, memo: dict) -> list:
if target_sum in memo.keys():
return memo[target_sum]
if target_sum == 0:
return []
if target_sum < 0:
return None
shortest_combination = None
for num in numbers:
remainder = target_sum - num
remainder_combination = best_sum(remainder, numbers, memo)
if remainder_combination is not None:
remainder_combination = remainder_combination.copy()
remainder_combination.append(num)
combination = remainder_combination
if (shortest_combination is None) or (len(combination) < len(shortest_combination)):
shortest_combination = combination
memo[target_sum] = shortest_combination
return shortest_combination
print(best_sum(7, [5, 2, 3, 7], memo={})) # [7]
print(best_sum(8, [2, 3, 5], memo={})) # [5, 3]
print(best_sum(8, [1, 4, 5], memo={})) # [4, 4]
print(best_sum(100, [1, 2, 5, 25], memo={})) # [25, 25, 25, 25]
canConstruct problem
Problem: write a function can_construct(target, word_bank) that accepts a target string and a list of strings. The function should return a boolean indicating whether or not the target can be constructed by concatenating elements of the word_bank list. You may reuse elements of the word_bank as many times as needed.
Python implementation of canConstruct problem
# O((n**m)*m)
def can_construct(target: str, word_bank: list) -> bool:
if target == '':
return True
for i in word_bank:
if target.startswith(i):
suffix = target[len(i):]
if can_construct(suffix, word_bank):
return True
return False
As in previous examples we need to pass an empty dict as memo to every function call.
# memoized O(n*(m**2))
def can_construct(target: str, word_bank: list, memo: dict) -> bool:
if target in memo.keys():
return memo[target]
if target == '':
return True
for i in word_bank:
if target.startswith(i):
suffix = target[len(i):]
if can_construct(suffix, word_bank, memo):
memo[target] = True
return True
memo[target] = False
return False
print(can_construct('abcdef', ['ab', 'abc', 'cd', 'def', 'abcd'], memo={})) # True
print(can_construct('skateboard', ['bo', 'rd', 'ate', 't', 'ska', 'sk', 'boar'], memo={})) # False
print(can_construct('enterapotentpot', ['a', 'p', 'ent', 'enter', 'ot', 'o', 't'], memo={})) # True
print(can_construct('eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeef', [
'e',
'ee',
'eee',
'eeee',
'eeeee',
'eeeeee'
], memo={})) # False
countConstruct problem
Problem: write a function count_construct(target, word_bank) that accepts a target string and a list of strings. The function should return the number of ways that the target can be constructed by concatenating elements of the word_bank list. You may reuse elements of the word_bank as many times as needed.
Python implementation of countConstruct problem
# O((n**m)*m)
def count_construct(target: str, word_bank: list) -> int:
if target == '':
return 1
total_count = 0
for word in word_bank:
if target.startswith(word):
suffix = target[len(word):]
total_count += count_construct(suffix, word_bank)
return total_count
# memoized O(n*(m**2))
def count_construct(target: str, word_bank: list, memo: dict) -> int:
if target in memo.keys():
return memo[target]
if target == '':
return 1
total_count = 0
for word in word_bank:
if target.startswith(word):
suffix = target[len(word):]
total_count += count_construct(suffix, word_bank, memo)
memo[target] = total_count
return total_count
print(count_construct('purple', ['purp', 'p', 'ur', 'le', 'purpl'], memo={})) # 2
print(count_construct('abcdef', ['ab', 'abc', 'cd', 'def', 'abcd'], memo={})) # 1
print(count_construct('skateboard', ['bo', 'rd', 'ate', 't', 'ska', 'sk', 'boar'], memo={})) # 0
print(count_construct('enterapotentpot', ['a', 'p', 'ent', 'enter', 'ot', 'o', 't'], memo={})) # 4
print(count_construct('eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeef', [
'e',
'ee',
'eee',
'eeee',
'eeeee',
'eeeeee'
], memo={})) # 0
allConstruct problem
Problem: write a function all_construct(target, word_bank) that accepts a target string and a list of strings. The function should return a 2D list containing all the ways that the target can be constructed by concatenating elements of the word_bank list. Each element of the 2D list should represent one combination that constructs the target. You may reuse elements of the word_bank as many times as needed.
Python implementation of allConstruct problem
Python implementation notes. The catch here is in implementing target_ways. We need to copy all sub-lists in a list. However, using list.copy() on nested lists will only copy the outer list while all sub-lists will keep pointing to the sub-lists in the original list. There are several ways to implement copy for nested lists in Python, I choose to use list comprehension with full slicing new_list = [sublist[:] for sublist in nested_list]
# O(n**m)
def all_construct(target: str, word_bank: list) -> list:
if target == '':
return [[]]
result = []
for word in word_bank:
if target.startswith(word):
suffix = target[len(word):]
suffix_ways = all_construct(suffix, word_bank)
target_ways = [el[:] for el in suffix_ways]
[el.insert(0, word) for el in target_ways]
result.extend(target_ways)
return result
# memoized O(n**m)
def all_construct(target: str, word_bank: list, memo: dict) -> list:
if target in memo.keys():
return memo[target]
if target == '':
return [[]]
result = []
for word in word_bank:
if target.startswith(word):
suffix = target[len(word):]
suffix_ways = all_construct(suffix, word_bank, memo)
target_ways = [el[:] for el in suffix_ways]
[el.insert(0, word) for el in target_ways]
# ret_target = [el[:] for el in target_ways]
result.extend(target_ways)
memo[target] = result
return result
print(all_construct('hello', ['cat', 'dog', 'mouse'], memo={})) # []
print(all_construct('', ['cat', 'dog', 'mouse'], memo={})) # [[]]
print(all_construct('purple', ['purp', 'p', 'ur', 'le', 'purpl'], memo={})) # [['le', 'purp'], ['le', 'p', 'ur', 'p']]
print(all_construct('abcdef', ['ab', 'abc', 'cd', 'def', 'abcd', 'ef', 'c'], memo={})) # [['ef', 'cd', 'ab'], ['def', 'c', 'ab'], ['def', 'abc'], ['ef', 'abcd']]
fib tabulation
Python implementation of Fibonacci problem using tabulation
# O(n)
def fib(n):
table = []
for i in range(n+1):
table.append(0)
table[1] = 1
for count in range(n):
table[count+1] += table[count]
if count < len(table)-2:
table[count+2] += table[count]
return table[n]
Grid traveller tabulation
Python implementation of Grid traveller problem using tabulation.
# O(m*n)
def grid_traveller(m, n):
table = []
for i in range(m+1):
table.append([0 for i in range(n+1)])
table[1][1] = 1
for i in range(m+1):
for j in range(n+1):
current = table[i][j]
if j+1 <= n:
table[i][j+1] += current
if i+1 <= m:
table[i+1][j] += current
return table[m][n]
canSum tabulation
Python implementation of canSum problem using tabulation.
# O(n*m)
def can_sum(target_sum: int, numbers: list) -> bool:
table = []
[table.append(False) for i in range(target_sum+1)]
table[0] = True
for i in range(len(table)):
if table[i]:
for num in numbers:
if (i+num) <= target_sum:
table[i+num] = True
return table[target_sum]
howSum tabulation
Python implementation of howSum problem using tabulation.
# O((m**2)*n)
def how_sum(target_sum: int, numbers: list) -> list:
table = [None for i in range(target_sum+1)]
table[0] = []
for i in range(target_sum):
if table[i] is not None:
for k in numbers:
if (i+k) <= target_sum:
table[i+k] = table[i].copy()
table[i+k].append(k)
return table[target_sum]
bestSum tabulation
Python implementation of bestSum problem using tabulation
# O((m**2)*n)
def best_sum(target_sum: int, numbers: list) -> list:
table = [None for i in range(target_sum+1)]
table[0] = []
for i in range(target_sum):
if table[i] is not None:
for num in numbers:
if (i+num) <= target_sum:
candidate = table[i].copy()
candidate.append(num)
if table[i+num] is None or (len(table[i+num]) > len(candidate)):
table[i+num] = candidate
return table[target_sum]
canConstruct tabulation
Python implementation of canConstruct problem using tabulation.
# O((m**2)*n)
def can_construct(target: str, words: list) -> bool:
table = [False for i in range((len(target)+1))]
table[0] = True
for i in range(len(target)):
if table[i]:
for word in words:
# if the word matches the characters starting at position i
if target[i:i+len(word)] == word:
table[i+len(word)] = True
return table[len(target)]
countConstruct tabulation
Python implementation of countConstruct problem using tabulation.
# O((m**2)*n)
def count_construct(target: str, words: list) -> int:
table = [0 for i in range(len(target)+1)]
table[0] = 1
for i in range(len(target)):
for word in words:
if word == target[i:(i + len(word))]:
table[i+len(word)] += table[i]
return table[len(target)]
allConstruct tabulation
Python implementation of allConstruct problem using tabulation
# O(n**m)
def all_construct(target: str, words: list) -> list:
table = [[] for i in range(len(target)+1)]
table[0] = [[]]
for i in range(len(target)):
for word in words:
if word == target[i:(i+len(word))]:
for el in table[i]:
temp = el[:]
temp.append(word)
table[i+len(word)].append(temp[:])
return table[len(target)]