# 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!