🎓 A1Learner
🔍

DSA DP Optimisations, Surveyed

DP optimisations narrow the range of split points worth trying in a table. Each one applies only when its stated condition holds.

A best split that moves right

Best splits for growing prefixes are listed. None of them moves left as the prefix grows.

best = [0, 0, 1, 1, 2, 3]
monotone = all(best[i] <= best[i + 1] for i in range(len(best) - 1))
print('best splits', best)
print('never moves left', monotone)

Checking the Knuth conditions aloud

Knuth needs the cost of a wider interval to bound its parts. The check below tests the two plain properties on one cost.

def cost(a, b):
    return (b - a) * (b - a)
q = cost(0, 2) + cost(1, 3) <= cost(0, 3) + cost(1, 2)
mono = cost(1, 2) <= cost(1, 3) <= cost(0, 3)
print('quadrangle step holds', q)
print('wider cost grows holds', mono)

A narrowed search range

A plain row tries five splits. Monotone splits narrow the next row to splits from 2 to 4.

plain = list(range(5))
narrowed = list(range(2, 5))
print('plain tries', len(plain), plain)
print('narrowed tries', len(narrowed), narrowed)

Example

values = [3, 1, 4, 1, 5, 9, 2, 6]
prefix = [0]
for v in values:
    prefix.append(prefix[-1] + v)

def cost(j, i):
    s = prefix[i] - prefix[j]
    return s * s

def plain(k):
    n = len(values)
    dp = [cost(0, i) for i in range(n + 1)]
    tries = 0
    for _ in range(2, k + 1):
        ndp = [10 ** 18] * (n + 1)
        for i in range(n + 1):
            for j in range(i):
                tries += 1
                ndp[i] = min(ndp[i], dp[j] + cost(j, i))
        dp = ndp
    return dp[n], tries

def fast(k):
    n = len(values)
    dp = [cost(0, i) for i in range(n + 1)]
    tries = 0
    def solve(layer, lo_i, hi_i, lo_j, hi_j, prev, cur):
        nonlocal tries
        if lo_i > hi_i:
            return
        mid = (lo_i + hi_i) // 2
        best_j, best_v = None, 10 ** 18
        for j in range(lo_j, min(mid, hi_j + 1)):
            tries += 1
            val = prev[j] + cost(j, mid)
            if val < best_v:
                best_v, best_j = val, j
        cur[mid] = best_v
        chosen = best_j if best_j is not None else lo_j
        solve(layer, lo_i, mid - 1, lo_j, chosen, prev, cur)
        solve(layer, mid + 1, hi_i, chosen, hi_j, prev, cur)
    for _ in range(2, k + 1):
        ndp = [10 ** 18] * (len(values) + 1)
        solve(_, 1, len(values), 0, len(values), dp, ndp)
        dp = ndp
    return dp[len(values)], tries

p_val, p_tries = plain(3)
f_val, f_tries = fast(3)
print('condition checked: best splits never move left')
print('plain value', p_val, 'tries', p_tries)
print('fast value', f_val, 'tries', f_tries)
print('match', p_val == f_val)

Key points

  • A split point is the place where the last piece of a solution begins
  • Divide and conquer optimisation needs split points that never move left
  • That condition is called monotonicity of the best split
  • Knuth optimisation needs a cost rule over intervals with two stated properties
  • The cost must satisfy the quadrangle inequality in plain words

In this example, eight values are split into three groups. The cost of a group is the square of its sum, which meets the monotonicity condition stated in the lesson. The plain table tries every split, and the narrowed table reuses the split range. Both tables give the same best value, and the try counts show the saving.

Note

Survey level means the conditions matter more than memorised code

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

Exercise

When may the divide and conquer optimisation be used?