This notebook contains a few canonically dynamic programming problems and demonstrates that they can be solved recursively.

Most Computer Science programs teach dynamic programming. You figure out your problem and you determine a recurrance relation for that problem which is usually a recursive formula. Then you take that recursive formula and turn it into this disgusting collection of nested loops that iterative populate this data structure until eventually you've calculated the answer in a bottom-up fashion.

Most Computer Science programs also teach recursion. You figure out your problem and you determine a recurrance relation for that problem which is usually a recursive formula. Then you take that recursive formula and write it in code. Then your teacher has you try to calculate the 100th fibinocci number and it takes forever. Then the teacher goes on to tell you that recursion is evil and that you should always use dynamic programming instead.

What your Computer Science program probably didn't tell you is that if you just cache the result of that recursive formula then you wouldn't have to wait so long to figure out the 100th fibinocci number.

Edit Distance

In [1]:
MISMATCH_COST = 2
GAP_COST = 1
In [2]:
"""
Edit distance using recursive approach
"""

import functools

@functools.lru_cache(maxsize=None)
def get_cost(a, b):
    """
    get_cost is memoized - prior computations are cached
    """
    if len(a) == 0:
        return len(b) * GAP_COST
    if len(b) == 0:
        return len(a) * GAP_COST
    
    if a[0] == b[0]:
        return get_cost(a[1:], b[1:])
    else:
        return min(
            get_cost(a[1:], b[1:]) + MISMATCH_COST,
            get_cost(a, b[1:]) + GAP_COST,
            get_cost(a[1:], b) + GAP_COST
        )
    
def print_edit_join(a, b):
    if not a and not b:
        pass
    elif not a:
        print("{}  {}".format("-", b[0]))
        print_edit_join(a, b[1:])
    elif not b:
        print("{}  {}".format(a[0], "-"))
        print_edit_join(a[1:], b)
    elif a[0] == b[0]:
        print("{}  {}".format(a[0], b[0]))
        print_edit_join(a[1:], b[1:])
    else:
        mismatch_cost = get_cost(a[1:], b[1:]) + MISMATCH_COST
        a_gap_cost = get_cost(a, b[1:]) + GAP_COST
        b_gap_cost = get_cost(a[1:], b) + GAP_COST
        
        if mismatch_cost < a_gap_cost and mismatch_cost < b_gap_cost:
            print("{}  {}".format(a[0], b[0]))
            print_edit_join(a[1:], b[1:])
        elif a_gap_cost < b_gap_cost:
            print("{}  {}".format("-", b[0]))
            print_edit_join(a, b[1:])
        else:
            print("{}  {}".format(a[0], "-"))
            print_edit_join(a[1:], b)

print_edit_join("corect", "correct")
c  c
o  o
r  r
-  r
e  e
c  c
t  t
In [3]:
"""
Classig Edit distance algorithm
"""

def dp_edit_distance(str_a, str_b):
    subsol = [[None for _ in range(len(str_b) + 1)] for _ in range(len(str_a) + 1)]
    
    """
    Populate the first row and col (represents the case where there
    is absolutely no commonality between the two strings)
    """
    for i in range(len(str_b) + 1):
        subsol[0][i] = i * GAP_COST
    for i in range(len(str_a) + 1):
        subsol[i][0] = i * GAP_COST
    
    for a_idx in range(len(str_a)):
        for b_idx in range(len(str_b)):
            if str_a[a_idx] == str_b[b_idx]:
                match_cost = subsol[a_idx][b_idx]
            else:
                match_cost = subsol[a_idx][b_idx] + MISMATCH_COST
                
            a_gap_cost = subsol[a_idx][b_idx + 1] + GAP_COST
            b_gap_cost = subsol[a_idx + 1][b_idx] + GAP_COST
            
            subsol[a_idx + 1][b_idx + 1] = min(match_cost, a_gap_cost, b_gap_cost)
                
    a_idx = len(str_a)
    b_idx = len(str_b)
    fmtstring = "{a_char}  {b_char}"
    print(fmtstring.format(a_char="A", b_char="B"))
    print("-" * len(fmtstring.format(a_char="A", b_char="B")))
    while a_idx > 0 or b_idx > 0:
        if a_idx == 0:
            b_idx -= 1
            print(fmtstring.format(a_char="-", b_char=str_b[b_idx]))
        elif b_idx == 0:
            a_idx -= 1
            print(fmtstring.format(a_char=str_a[a_idx], b_char="-"))
        else:
            match_cost = subsol[a_idx - 1][b_idx - 1] + (
                MISMATCH_COST if str_a[a_idx - 1] != str_b[b_idx - 1] else 0)
            a_gap_cost = subsol[a_idx - 1][b_idx] + GAP_COST
            b_gap_cost = subsol[a_idx][b_idx - 1] + GAP_COST
            
            if match_cost < a_gap_cost and match_cost < b_gap_cost:
                a_idx -= 1
                b_idx -= 1
                print(fmtstring.format(a_char=str_a[a_idx], b_char=str_b[b_idx]))
            elif a_gap_cost < b_gap_cost:
                a_idx -= 1
                print(fmtstring.format(a_char=str_a[a_idx], b_char="-"))
            else:
                b_idx -= 1
                print(fmtstring.format(a_char="-", b_char=str_b[b_idx]))
                
dp_edit_distance("apple", "aple")
A  B
----
e  e
l  l
p  -
p  p
a  a

Fibonocci

In [4]:
"""
Recursive fibonocci number
"""

@functools.lru_cache(maxsize=None)
def rec_fib(n):
    if n < 2:
        return 1
    else:
        return rec_fib(n - 2) + rec_fib(n - 1)
    
print(rec_fib(100))
573147844013817084101
In [5]:
"""
Dynamic Programming fibonocci number
"""

def dp_fib(n):
    subsol = [None for _ in range(n + 1)]
    subsol[0] = subsol[1] = 1
    for i in range(2, n + 1):
        subsol[i] = subsol[i - 1] + subsol[i - 2]
    return subsol[n]
    
print(dp_fib(100))
573147844013817084101

Knapsack

In [6]:
from collections import namedtuple
Item = namedtuple("Item", ["name", "weight", "value"])

KNAPSACK_ITEMS = [
    Item(name="...Baby One More Time", weight=10, value=60),
    Item(name="Oops!... I Did it Again", weight=20, value=100),
    Item(name="Britney", weight=30, value=75),
    Item(name="In the Zone", weight=30, value=150),
    Item(name="Blackout", weight=40, value=200),
    Item(name="Circus", weight=35, value=190),
    Item(name="Femme Fatale", weight=30, value=180),
    Item(name="Britney Jean", weight=40, value=120),
    Item(name="Glory", weight=25, value=150),
]

MAX_CAPACITY=110
NUM_ITEMS=len(KNAPSACK_ITEMS)
In [7]:
"""
Recursive Knappsack problem
"""

@functools.lru_cache(maxsize=None)
def rec_knapsack(capacity, num_items):
    if capacity == 0:
        return 0
    elif num_items == 0:
        return 0
    elif KNAPSACK_ITEMS[num_items - 1].weight > capacity:
        return rec_knapsack(capacity, num_items - 1)
    else:
        nth_item = KNAPSACK_ITEMS[num_items - 1]
        return max(
            rec_knapsack(capacity - nth_item.weight, num_items - 1) + nth_item.value,
            rec_knapsack(capacity, num_items - 1)
        )
    
rec_knapsack(MAX_CAPACITY, NUM_ITEMS)
Out[7]:
620
In [8]:
"""
Dynamic Programming Knappsack problem
"""

def dp_knapsack(capacity_max, num_items):
    subsol = [[0 for _ in range(capacity_max + 1)] for _ in range(num_items + 1)]
    
    for item_idx in range(1, num_items + 1):
        for capacity in range(1, capacity_max + 1):
            nth_item = KNAPSACK_ITEMS[item_idx - 1]
            if capacity < nth_item.weight:
                subsol[item_idx][capacity] = subsol[item_idx - 1][capacity]
            else:
                subsol[item_idx][capacity] = max(
                    subsol[item_idx - 1][capacity - nth_item.weight] + nth_item.value,
                    subsol[item_idx - 1][capacity],
                )
    
    return subsol[num_items][capacity_max]

dp_knapsack(MAX_CAPACITY, NUM_ITEMS)
Out[8]:
620