Some DP problems in Python

dp.py

def ugly_pascal_triangle(level):
    table = []
    for row in range(level):
        for col in range(level):
            if row == 0:
                table.append([])
            if col == 0 or row == col:
                table[row].append(1)
            elif col <= row:
                table[row].append(table[row-1][col] + table[row-1][col-1])

def slightly_better_pascal_triangle(level):
    table = []
    for row, col in [(r, c) for r in range(level) for c in range(level)]:
        if row == 0:
            table.append([])
        if col == 0 or row == col:
            table[row].append(1)
        elif col <= row:
            table[row].append(table[row-1][col] + table[row-1][col-1])

def valid_indices(row, col=None):
    if col is None:
        col = row
    return [(r, c) for r in range(row) for c in range(col)]

def pascal_triangle(level):
    """ 
    Generate pascal triangle using these rules
    (1) table[_][0] and table[i][j] will always be 1
    (2) table[i][j] = table[i-1][j] + table[i-1][j-1]
    """
    def compute(table, row, col):
        if row == 0:
            table.append([])
        if col == 0 or row == col:
            table[row].append(1)
        elif col <= row:
            table[row].append(table[row-1][col] + table[row-1][col-1])

    table = []
    [compute(table, r, c) for r, c in valid_indices(level)] 
    print(table)

def best_pascal_triangle(level):
    table = []
    for r in range(level):
        table.append([1] + [table[r-1][c] + table[r-1][c-1] for c in range(1, r)] 
                + ([1] if r else []))
    print(table)

class cell:
    parent = None
    def __init__(self, cost):
        self.cost = cost

def edit_distance(source, target):
    # Degenerate Cases
    if source == target :
        return 0
    if len(source) == 0:
        return len(target)
    if len(target) == 0:
        return len(source) 
    # Previous Row
    v0 = list(range(len(target) + 1)) 
    v1 = [0] * (len(target) + 1) 

    for i in range(len(source)):
        v1[0] = i + 1

        for j in range(len(target)):
            cost = 0 if source[i] == target[j] else 2
            v1[j + 1] = min(v1[j] + 1,\
                            v0[j + 1] + 1,\
                            v0[j] + cost)

        for j in range(len(v0)):
            v0[j] = v1[j]

    return v1[len(target)]

 

if __name__ == "__main__":
    print(edit_distance("Illinois", "Illicit"))