Divide and Conquer DP Optimization: Quadrangle Inequality & Knuth Optimization

Divide and Conquer DP Optimization applies to recurrences of the form $dp[i][j] = min_{k < j} (dp[i - 1][k] + C(k + 1, j))$ whenever the optimal split point $opt[i][j]$ is monotonically non-decreasing in $j$: $opt[i][j] le opt[i][j + 1]$.

1. The Recursive Divide and Conquer Solver

void solve(int i, int l, int r, int opt_l, int opt_r) {
    if (l > r) return;
    int mid = (l + r) / 2;
    int best_k = opt_l;
    dp[i][mid] = INF;
    
    for (int k = opt_l; k <= min(mid - 1, opt_r); ++k) {
        long long val = dp[i - 1][k] + cost(k + 1, mid);
        if (val < dp[i][mid]) {
            dp[i][mid] = val;
            best_k = k;
        }
    }
    
    solve(i, l, mid - 1, opt_l, best_k);
    solve(i, mid + 1, r, best_k, opt_r);
}