Lessons from D&C Optimization

$1.$ D&C improvement works for layered DP: $dp[g][i] = \min_{j < i}(dp[g-1][j] + cost(j,i))$.

$2.$ Prove QI holds, which implies monotonicity of optimal splits.

$3.$ Solve middle first, then recurse with bounded search ranges.

$4.$ Each recursion level does $O(n)$ work. Total: $O(n \log n)$ per layer. The pattern: partition problems, layer-by-layer DP, cost satisfying QI. Apply these patterns when you encounter similar problems.