Divide & Conquer - DP

Authors: Andi Qu, Benjamin Qi

Using Divide & Conquer as a DP Optimization.


Consider a dynamic programming problem with the following formula

dp(i,j)=min0kj(dp(i1,k1)+C(k,j)),dp(i,j) = \min_{0\leq k \leq j} ( dp(i-1, k-1) + C(k,j)),

where C(i,j)C(i,j) is a cost function and you can compute it in O(1)O(1) time. Furthermore, dp(i,j)=0dp(i,j) =0 for j<0j<0.

The straightforward implementation gives a runtime of O(MN2)O(MN^2) if 0i<M0\leq i < M and 0j<N0\leq j < N. Divide & Conquer DP allows this to be optimized to O(MNlogN)O(M N \log N).

For each i,ji,j, let opt(i,j)\text{opt}(i,j) be the value of kk that minimizes the right hand side of the equation. Divide & Conquer DP only applies if

opt(i,j)opt(i,j+1).\text{opt}(i,j) \leq \text{opt}(i,j+1).

Often, proving this with the given cost function is challenging, but if the cost function satisfies the quadrangle inequality, the condition holds.

We can then apply the idea behind Divide & Conquer. Fix a given ii. First, compute opt(i,n/2)\text{opt}(i,n/2). Then compute opt(i,n/4)\text{opt}(i, n/4) using the fact that it is less than or equal to opt(i,n/2)\text{opt}(i, n/2). Similarly, we can compute opt(i,3n/4)\text{opt}(i, 3n/4) and recursively split the ranges in half, keeping track on the lower and upper bounds.

Since each possible value of opt(i,j)\text{opt}(i, j) appears O(logn)O(\log n) times, this gives a final runtime of O(mnlogn)O(mn \log n).

Example - Circular Barn

Focus Problem – try your best to solve this problem before continuing!

View Internal Solution

You should already be familiar with the CHT solution.


We iterate through the possibilities of the location of the first door. For each of the first doors, we can now view the barn linearly. All further calculations will be done assuming the barn is a linear sequence of doors starting at the first opened door.

Let dp(i,k)dp(i,k) denote the location of the last door if we place kk doors optimally among the first ii rooms. The idea is that dp(i,k)dp(i+1,k)dp(i,k) \leq dp(i+1, k). Assume this was not true for the sake of contradiction. Then dp(i,k)>dp(i+1,k)dp(i,k) > dp(i+1,k), so we also have dp(i+1,k)idp(i+1,k) \leq i. But then we could have used the best possible setup for (i+1,k)(i+1,k) in the (i,k)(i,k) setup as well, since all open doors are among the first ii rooms anyways.

Since the monotonicity condition is held, we can now perform Divide & Conquer DP. Fix the value of kk and compute dp(n/2,k)dp(n/2, k). Then compute it for the left and right halves of the array.


Time Complexity: O(n2klogn)\mathcal{O}(n^2 k \log n), since we need to check nn rooms for the optimal first barn position.


#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MAX_N = 1000;
const int MAX_K = 7;
// calc[i][j] stores the # of steps to get all cows distance j away to door i
// to make implementing a cyclic array easier, we double the size
vector<vector<ll>> calc(2 * MAX_N, vector<ll>(MAX_N + 1, 0));


StatusSourceProblem NameDifficultyTags
Show TagsD&C, DP
Show TagsD&C, DP
Show TagsD&C, DP
Show TagsD&C, DP
Show TagsD&C, DP
Show TagsD&C, DP
POIVery Hard
Show TagsD&C, DP
IOIVery Hard
Show TagsD&C, DP
PlatinumVery Hard
Show TagsD&C, DP
JOIVery Hard
Show TagsD&C, DP

JOI Bubblesort English Statement: You are given an array of length NN (1N100,000)(1 \le N \le 100,000). You must choose two numbers in this array and swap them. After swapping these two numbers, you sort the array using a bubble sort algorithm. What is the minimum number of bubble sort swaps necessary, assuming you choose the two initial numbers to swap optimally? The two initial numbers that you swap do not count towards the minimum number of bubble sort swaps.

Module Progress:

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!