DP Speedups (Knuth, Convex Hull Trick, Aliens)

Convex hull trick, Knuth optimization, and Aliens trick shrink polynomial factors on special recurrences—only apply after proving required structure.

Why this shows up in the real world

Competitive programming libraries ship CHT for linear transitions. Operations research uses similar tricks.

Core idea (explained for students)

Know templates exist; first write O(n^2) DP, profile, then swap in optimization with tests proving equivalence.

Try this in Python

def linear_dp_best(a: list[int]) -> int:
    best = -10**18
    cur = 0
    for x in a:
        cur = max(x, cur + x)
        best = max(best, cur)
    return best


print(linear_dp_best([3, -2, 5, -1]))

Common mistakes

• Wrong convexity assumptions on cost functions.
• Integer overflow in slope comparisons.

Key takeaways

• Keep brute reference for random small tests when swapping in CHT.