Divide and Conquer DP Optimization

D&C on DP speeds transitions when cost functions satisfy quadrangle inequality or monotonicity—split ranges of decisions and merge (Aliens trick, Knuth optimization).

Why this shows up in the real world

Optimal polygon triangulation and some scheduling DP benefit from divide-and-conquer speedups.

Core idea (explained for students)

Recurrence dp[i][j] = min_k (dp[i][k]+dp[k][j])+C[i][j] with monotone argmin k allows Knuth/Yao speedup when proven.

Try this in Python

def fib(n: int, memo: dict[int, int] | None = None) -> int:
    if memo is None:
        memo = {}
    if n <= 1:
        return n
    if n in memo:
        return memo[n]
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
    return memo[n]


print(fib(30))

Common mistakes

• Applying Knuth without verifying quadrangle inequality—silent wrong answers.
• Off-by-one on split point k.

Key takeaways

• Prove monotone opt on paper before coding optimized version.
• Keep naive DP for small n to cross-check.