Purfe

Learn, create and have fun with Python

Dynamic Programming – Learn to Solve Algorithmic Problems & Coding Challenges. Python code

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

  1. Fibonacci problem
  2. Grid traveller problem
  3. canSum problem
  4. howSum problem
  5. bestSum problem
  6. canConstruct problem
  7. countConstruct problem
  8. allConstruct problem
  9. fib tabulation
  10. Grid traveller tabulation
  11. canSum tabulation
  12. howSum tabulation
  13. bestSum tabulation
  14. canConstruct tabulation
  15. countConstruct tabulation
  16. 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

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
Python

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

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
Python

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

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
Python

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

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
Python

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

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]
Python

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
Python

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
Python

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
Python

# 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
Python

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
Python

# 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']]
Python

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]
Python

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]
Python

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]
Python

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]
Python

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]
Python

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)]
Python

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)]
Python

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)]
Python

Prev post Pandas DataFrame Memory Optimization With FrogID
Next post 6 ways to solve Fibonacci problem. Python

Related Posts

Leave a Reply

Your email address will not be published. Required fields are marked *

Back to top