4.6

gistfile1.py

DP(i,j):
    soln = i*n array with val inited to -1
    return helper(i,j, soln)

helper(i, j, soln):
    #first iterate through all the smallest lens, then build on those
    for 1 to (j-i) as len:      
        #make j always len away from i
        j = i + len - 1
        bestsofar = infin
        for i to j as k:
            value = max(soln_check(soln, i, k-1), soln_check(soln, k+1, j)) + cost(k)
            if value > bestsofar:
                bestsofar = value

    return soln[i][j] 

soln_check(soln, i, j):
    if j < i:
        return 0
    if i == j:
        return cost(j)
    else:
        return soln[i][j]