adv mic

#######################################################
"""
This is an O(n^3) algorithm. ==> Top down
"""

def func(a, b):
    if a == b: return ...
    if solved[(a, b)]: return sol[(a, b)]
    solved[(a, b)] = True

    ans = INF

    for k in xrange(a, b):
        ans = min(ans, func(a, k) + func(k + 1, b))

    sol[(a, b)] = ans

#######################################################
"""
This is an O(n^3) algorithm. ==> Bottom up
"""

# base case
for i in xrange(0, n):
    sol[(i, i)] = ...

for w in xrange(1, n):
    for i in xrange(0, n - w):
        j = i + w
        ans = INF

        for k in xrange(i, j):
            ans = min(ans, sol[(i, k)] + sol[(k + 1, j)])

        sol[(i, j)] = ans

#######################################################
"""
This is an O(n^2) algorithm. ==> Bottom up + adv mic
"""

# base case
for i in xrange(0, n):
    sol[(i, i)] = ...
    K[(i, i)] = i

for w in xrange(1, n):
    for i in xrange(0, n - w):
        j = i + w
        ans = INF

        for k in xrange(K[i][j - 1], K[i + 1][j]):
            ans = min(ans, sol[(i, k)] + sol[(k + 1, j)])
            if ans == sol[(i, k)] + sol[(k + 1, j)]:
                K[i][j] = k

        sol[(i, j)] = ans

#######################################################