DP optimisations

The time of a DP is the number of states times the work per state. Some rules look at many earlier states and keep the best one. When the best choice moves in a predictable way, most of those looks can be skipped. This lesson collects the speed-ups that do that, with the conditions that make each one safe.

Where the time goes

The DPs of this station and of DYNP have a rule of the form “the best over all choices k of (earlier answer for k + cost of the step)”. With n states and up to n choices each, that is O(n²) (n · n); with a table of stretches (lesson 3), O(n³) (n · n · n). The four speed-ups below all keep the same states and the same answers. They only stop looking at choices that can be proved not to win.

A sliding window of choices

When the choices for state i are the last k states, best[i] is a[i] plus the largest of best[i − k] to best[i − 1], and the window of choices slides one step at a time. STAQ-6’s monotonic deque keeps the window’s maximum in O(1) per step on average, so the whole DP costs O(n) instead of O(n · k). DYNP-4 used it this way. The other speed-ups work the same way: a structure, or a proof, that tells which choices are still worth looking at.

Knuth’s rule for interval DP

In joining piles (lesson 3), let opt[i][j] be the split k that gives best[i][j] (the smallest such k when there are ties). Knuth (1971) noticed that the split moves in one direction as the stretch grows:

So, when filling by length, only k from opt[i][j − 1] to opt[i + 1][j] need to be tried; both are already in the table. Step through the first version of the figure.

Why it is O(n²). For one length L, the ranges of the cells i = 0, 1, 2, … are opt[i][i + L − 2] … opt[i + 1][i + L − 1]. The end of one range is the start of the next, so the range sizes add up to the last end minus the first start, plus 1 for each cell: at most 2n. With n lengths, that is O(n²) in all.

When it holds. F. Yao (1980) proved the rule for the joining table of lesson 3 with any step cost w(i, j) in place of the pile sum, whenever w has two properties: it does not shrink when the stretch grows (a stretch inside another costs no more), and w(a, c) + w(b, d) ≤ w(a, d) + w(b, c) for a ≤ b ≤ c ≤ d, called the quadrangle inequality: two overlapping stretches cost no more than the outer and the inner one. The sum of a stretch meets both with equality. The proof is an exchange argument on the two splits; this course only states it. For a new cost, test the rule against the plain O(n³) table on random small inputs before trusting it.

from itertools import accumulate

def join_cost_knuth(a):
    n = len(a)
    if n < 2:
        return 0
    pre = [0, *accumulate(a)]
    best = [[0] * n for _ in range(n)]
    opt = [[i] * n for i in range(n)]    # the best split; opt[i][i] = i
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            lo, hi = opt[i][j - 1], min(opt[i + 1][j], j - 1)
            b, at = float("inf"), lo
            for k in range(lo, hi + 1):  # only the splits Knuth's rule allows
                c = best[i][k] + best[k + 1][j]
                if c < b:
                    b, at = c, k
            best[i][j] = b + pre[j + 1] - pre[i]
            opt[i][j] = at
    return best[0][n - 1]

Cutting a rail (ADDP-P3) has the same shape, so it can be made O(n²) this way too; the practice problem is small enough for the plain table.

Divide and conquer over split points

Another common shape: split a row of n items into g stretches, and pay a cost C(i, j) for each stretch of items i to j − 1. With layer[j] the best way to split the first j items into the stretches so far, each new layer is

which is O(n²) per layer. When C meets the quadrangle inequality, the best i for j never moves left as j grows. Then:

1. work out the middle j by trying every allowed i, and note the best one, at;
2. every j to its left has its best i at or before at, and every j to its right at or after it;
3. solve the two halves the same way, each with its narrower range.

from itertools import accumulate

def split_cost(a, g):
    """Split a into at most g stretches; a stretch costs the square of its sum."""
    n = len(a)
    pre = [0, *accumulate(a)]
    cost = lambda i, j: (pre[j] - pre[i]) ** 2        # the stretch a[i:j]
    INF = float("inf")
    prev = [0] + [INF] * n               # 0 stretches: only the empty start
    for _ in range(g):
        cur = [INF] * (n + 1)

        def solve(lo, hi, olo, ohi):     # fill cur[lo..hi]; their splits lie in olo..ohi
            if lo > hi:
                return
            mid = (lo + hi) // 2
            best, at = INF, olo
            for i in range(olo, min(mid, ohi) + 1):
                c = prev[i] + cost(i, mid)
                if c < best:
                    best, at = c, i
            cur[mid] = best
            solve(lo, mid - 1, olo, at)  # to the left, the split is at most at
            solve(mid + 1, hi, at, ohi)  # to the right, at least at
        solve(0, n, 0, n)
        prev = cur
    return prev[n]

Cost. On each level of the recursion the ranges of i overlap only at their ends, so a level costs O(n), and there are about log₂ n levels (the number of times n can be halved). So a layer costs O(n log n) and the whole DP O(g · n log n), against O(g · n²). The recursion is only log₂ n deep.

Lines on a hull

A train stops at some of n stations at positions x₀ < x₁ < …. A run from stop i to stop j costs (xⱼ − xᵢ)² + c. Then best[j] is the smallest best[i] + (xⱼ − xᵢ)² + c. Multiply out the square:

For each earlier stop i, the part in brackets is a straight line m · X + b with slope m = −2xᵢ and height b = best[i] + xᵢ², read at X = xⱼ. So each step asks: of all the lines so far, which is lowest at this X? The lowest line at each X forms the lower edge of all the lines, which is convex (GEOM-3); lines that are never lowest can be thrown away. This is often called the convex hull method for DP.

Here the slopes fall as stops are added (positions rise), and the questions come at rising X. Then the useful lines can be kept in a deque, as the second version of the figure shows:

• Adding a line at the back: the last kept line is useless if the new line passes under the line before it no later than the last one does. Remove it and check again. Compare crossing points with whole numbers by multiplying across, never by dividing.
• A question at X: while the second line is at least as low as the first at X, remove the first. Questions only move right, so it will never be needed again. The answer is the first line.

Each line enters once and leaves at most once: O(n) for the whole DP instead of O(n²). That is the practice problem.

Which speed-up when

In every case, check the condition, or check the fast version against the plain one on many small random inputs. A speed-up used where its condition fails gives wrong answers with no error to warn you.

Now try ADDP-P6, The cheapest trip.