Skip to content

Divide and Conquer DP

Divide and Conquer is a dynamic programming optimization.

Preconditions

Some dynamic programming problems have a recurrence of this form: \(\(dp(i, j) = \min_{0 \leq k \leq j} \\{ dp(i - 1, k - 1) + C(k, j) \\}\)\), where \(C(k, j)\) is a cost function and \(dp(i, j) = 0\) when \(j \lt 0\).

Say \(0 \leq i \lt m\) and \(0 \leq j \lt n\), and evaluating \(C\) takes \(O(1)\) time. Then the straightforward evaluation of the above recurrence is \(O(m n^2)\). There are \(m \times n\) states, and \(n\) transitions for each state.

Let \(opt(i, j)\) be the value of \(k\) that minimizes the above expression. Assuming that the cost function satisfies the qudrangle inequality, we can show that \(opt(i, j) \leq opt(i, j + 1)\) for all \(i, j\). This is known as the monotonicity condition. Then, we can apply divide and conquer DP. The optimal "splitting point" for a fixed \(i\) increases as \(j\) increases.

This lets us solve for all states more efficiently. Say we compute \(opt(i, j)\) for some fixed \(i\) and \(j\). Then for any \(j' < j\) we know that \(opt(i, j') \leq opt(i, j)\). This means when computing \(opt(i, j')\), we don't have to consider as many splitting points!

To minimize the runtime, we apply the idea behind divide and conquer. First, compute \(opt(i, n / 2)\). Then, compute \(opt(i, n / 4)\), knowing that it is less than or equal to \(opt(i, n / 2)\) and \(opt(i, 3 n / 4)\) knowing that it is greater than or equal to \(opt(i, n / 2)\). By recursively keeping track of the lower and upper bounds on \(opt\), we reach a \(O(m n \log n)\) runtime. Each possible value of \(opt(i, j)\) only appears in \(\log n\) different nodes.

Note that it doesn't matter how "balanced" \(opt(i, j)\) is. Across a fixed level, each value of \(k\) is used at most twice, and there are at most \(\log n\) levels.

Generic implementation

Even though implementation varies based on problem, here's a fairly generic template. The function compute computes one row \(i\) of states dp_cur, given the previous row \(i-1\) of states dp_before. It has to be called with compute(0, n-1, 0, n-1). The function solve computes m rows and returns the result.

int m, n;
vector<long long> dp_before(n), dp_cur(n);

long long C(int i, int j);

// compute dp_cur[l], ... dp_cur[r] (inclusive)
void compute(int l, int r, int optl, int optr) {
    if (l > r)
        return;

    int mid = (l + r) >> 1;
    pair<long long, int> best = {LLONG_MAX, -1};

    for (int k = optl; k <= min(mid, optr); k++) {
        best = min(best, {(k ? dp_before[k - 1] : 0) + C(k, mid), k});
    }

    dp_cur[mid] = best.first;
    int opt = best.second;

    compute(l, mid - 1, optl, opt);
    compute(mid + 1, r, opt, optr);
}

int solve() {
    for (int i = 0; i < n; i++)
        dp_before[i] = C(0, i);

    for (int i = 1; i < m; i++) {
        compute(0, n - 1, 0, n - 1);
        dp_before = dp_cur;
    }

    return dp_before[n - 1];
}

Things to look out for

The greatest difficulty with Divide and Conquer DP problems is proving the monotonicity of \(opt\). One special case where this is true is when the cost function satisfies the quadrangle inequality, i.e., \(C(a, c) + C(b, d) \leq C(a, d) + C(b, c)\) for all \(a \leq b \leq c \leq d\). Many Divide and Conquer DP problems can also be solved with the Convex Hull trick or vice-versa. It is useful to know and understand both!

Practice Problems

References