Some solutions for some dynamic programming problems.

dp.py

def build_adj_matrix(arr):
    """ 
    Returns an adjacency matrix where elements a_0..a_i
    , where i < j, are considered adjacent to a_j if
    a_i < a_j.
    """
    result = {}
    for i in xrange(len(arr)):
        result[i] = []
        for j in xrange(i):
            if arr[j] < arr[i]:
                result[i].append(j)
    return result
     
def longest_inc_subseq(arr):
    dag = build_adj_matrix(arr)
    lengths = {} # {index -> (length, predecessor)}
    for j in xrange(len(arr)):
        pre_lens = [(lengths[pre][0], pre) for pre in dag[j]]
        pre_t = (0, None)
        if len(pre_lens) != 0:
            pre_t = max(pre_lens)
        lengths[j] = (1 + pre_t[0], pre_t[1])
        
    max_i = max(lengths, key=lambda k : lengths[k][0])
    result = [arr[max_i]]
    pre = lengths[max_i][1]
    while pre != None:
        result.append(arr[pre])
        pre = lengths[pre][1]
        
    return result

def knap_sack(items, w):
    """
    Returns maximum potential dolar value a knapsack of capacity 'w'
    can hold, given 'items' where each item is tuple (weight, value)
    """
    k = [0]*(w+1)
    for w_i in range(1, w+1):
        p = []
        for item in items:
            if item[0] <= w_i:
                p.append(item[1] + k[w_i - item[0]])
        if len(p) != 0:
            k[w_i] = max(p)
    return k[w]
    
def knap_sack_no_rep(items, W):
    k = [[0] * (W + 1)] * (len(items) + 1)
    for w in xrange(1, W + 1):
        for j in range(1, len(items)):
            item = items[j-1]
            if item[0] <= w:
                k[j][w] = max(k[j - 1][w - item[0]] + item[1], k[j - 1][w])
            else:
                k[j][w] = k[j-1][w]
    return k[len(items)][W]
    
print knap_sack_no_rep([(6,30), (3,14), (4,16), (2,9)], 10)