This blog is not exactly a tutorial, it is more of a review of the techniques that can be used solve some DP problems involving the quadrangle inequality, and some problems related to DNC DP.

DNC DP

DNC DP is a well-known optimisation that can solve some DP problems from $$$O(N^2K)$$$ time to $$$O(NKlogN)$$$ time. The key idea uses the monotonic nature of the splitting points to compute each layer in $$$O(NlogN)$$$ time. In other words, it uses the fact that $$$opt(N,K)<=opt(N+1,K)$$$, where $$$opt(N,K)$$$ is defined as the left splitting point for the $$$K^{th}$$$ segment for the first $$$N$$$ elements, for all positive integers $$$N$$$ and $$$K$$$. Most often, the monotonic nature is satisfied when the cost function satisfies the quadrangle inequality (a.k.a. wider is worse), which is for all indices $$$A<=B<=C<=D$$$, $$$cost(A,C)+cost(B,D)>=cost(A,D)+cost(B,C)$$$ (it can also work the other way).

Guards

Given an array of length $$$N$$$, split it into $$$K$$$ segments such that $$$\sum_{i=1}^K$$$ (length $$$\cdot$$$ sum) is minimised. This problem can be considered classic, and has been explored by other guides talking about DNC DP. To solve, just notice that the cost function satisfies the quadrangle inequality. Convince yourself that it is true. Hence, we can use DNC DP on this problem.
The code is actually pretty simple, and can be found here.

Monge + 1D-1D DP

Two other implications of quadrangle inequality are:
- Monge can be done
- 1D-1D DP Optimisation can be done
By combining these two techniques, we can solve some DNC DP problems in $$$O(Nlog^2N)$$$ time, cutting out the $$$K$$$ factor. Let's now explain how this works.

First, we apply Monge, and transform the problem into:
Given an array of length $$$N$$$ and a cost $$$K$$$ for each segment, split it into as many segments as you want, such that $$$\sum_{i=1}^X$$$ (length $$$\cdot$$$ sum) is minimised, where $$$X$$$ is the number of segments in the end.

Our DP function becomes $$$dp[i] = \min_{1 \leq j \leq i} \{ dp(j-1) + C(j, i) + K \}$$$ which is then a function that can be solved in $$$O(NlogN)$$$ time using 1D-1D DP optimisation. Read the dedicated blog for more details. Since we solve this problem at most $$$O(logN)$$$ times due to our use of Monge, hence we achieve an $$$O(Nlog^2N)$$$ time complexity, beating DNC DP.

A sample implementation of this for Guards is provided here.

This technique is known, I first learnt about it when browsing the fastest submission on 321E - Ciel and Gondolas. However, a major caveat of this method is that the cost function must be able to be computed in $$$O(1)$$$/very quickly, or else there will be issues, seen in the next section.

When Monge Fails

Consider 868F - Yet Another Minimization Problem. We can use DNC DP to solve this, but we need to slightly modify it. Because computing the cost function is no longer $$$O(1)$$$, we need to use Mo-like two pointer method to move them to a desired range to compute our costs. In the end, the total number of moves we need to make is bounded by $$$O(NKlogN)$$$, due to how the structure of DNC DP works. However, if we compare this to 1D-1D DP, the structure with which we compute the answers do not help. The best we can do is $$$O(Nlog^2N\sqrt{N})$$$. Combined with the fact that this has bad constant time, we end up with a more complex and also more expensive solution than DNC DP. This sort of problem still gives DNC DP its use.

Although not common, there is one example of a problem that does not satisfy quadrangle inequality but works with DNC DP (although not optimal). problem
Given the numbers $$$1$$$ to $$$N$$$, you can guess a number $$$X$$$. This guess costs $$$X$$$ and you will be told if your guess is higher than, lower than or equal to the correct answer. The final cost is the sum of costs before you get the equal answer. Find the minimal final cost of the worst case in a series of guesses.

There exists a simpler $$$O(N^2)$$$ solution, but we shall explore the DNC DP solution.

Define $$$dp(N,K)$$$ as the minimal cost of the segment $$$[1+K,2+K,3+K,...N+K]$$$. Then, we get $$$dp(N,K) = \min_{1 \leq i \leq N} \{ dp(i-1,K) + dp(N-i,K+i) + i + K \}$$$.

If we set $$$opt(N,K)$$$ as the optimal choice of $$$i$$$ for $$$dp(N,K)$$$, then we have that $$$opt(N,K)>=opt(N,K+1)$$$. In other words, I claim that the optimal choice of a splitting point starts from the right and shift towards the centre monotonically. This can be proven rigorously, but I am lazy. Intuitively, the idea is that as $$$K$$$ increases, the more that $$$N$$$ doesn't matter, since the elements become more and more "close". Hence, the optimal strategy tends towards a binary search. When $$$K$$$ is low compared to $$$N$$$, the elements have a much larger difference in magnitude, and it is preferred to start more towards the right. Because of this property, we can apply DNC DP to solve this problem.

For this problem, it is not clear how Monge + 1D-1D DP may be used, even though DNC DP is usable. Do you know of any other problems that are like this?

Conclusion

Although Monge + 1D-1D DP is more powerful than DNC DP when cost function can be computed in $$$O(1)$$$ time, DNC DP is not totally useless. Hopefully, we will see more interesting problems on DNC DP in the future, which have more steps before applying the classic algorithm.