Introduction to DP Optimization

Introduction

This page lists some common dynamic programming (DP) optimization methods. DP optimization refers to the fact that although it is easy to write the naive state transition equations for many dynamic programming problems, direct computation is often inefficient, so some techniques are needed to reduce the time complexity.

These methods are closely related, often contain similar ideas, and frequently need to be used together with multiple techniques. Therefore, this article only provides a rough classification and focuses on introducing some of the most basic ideas.

Optimizing with common techniques

The transitions of many dynamic programming problems can be optimized using common algorithms and data structures.

There are two common situations for this type of technique. In the first, the DP problem has a state transition equation of the following form:

$$f(i) = F(a_i,\{f(j) : j < i\}).$$

Here, computing the current state $f(i)$ depends on the current input $a_i$ and the states of the entire preceding sequence $\{f(j):j < i\}$. Therefore, we can maintain a data structure, regard each computation of $f(i)$ as a query operation, and then perform an update operation after obtaining the current state $f(i)$ to update the data structure for subsequent transitions.

In the second situation, the DP problem has a state transition equation of the following form:

$$f(i,\cdot) = F(a_i,f(i-1,\cdot)).$$

Here, each $f(i,\cdot)$ is an array or another more complex object. Therefore, although $f(i,\cdot)$ depends only on the single preceding state, a single transition is highly complex and needs to be optimized using techniques such as data structures.

Prefix-sum optimization of DP

Related page: Prefix Sum

If computing the current state depends on the sum of a subsegment of previous states, prefix sums can be maintained to speed up the computation. Problems involving multidimensional prefix sums are also called SOS DP.

Exercises:

• Luogu P2513 [HAOI2009] Inversion Sequence
• AtCoder Educational DP Contest M - Candies

Monotone queue/monotone stack optimization of DP

Main page: Monotone Queue/Monotone Stack Optimization

If the current state depends on information such as the range extrema of previous states, a monotone queue or monotone stack can be maintained to speed up the computation.

Segment tree/Fenwick tree optimization of DP

Related pages: Segment Tree, Fenwick Tree

If every state transition queries sums, extrema, or similar information over a range, or a single update involves a range update, a segment tree or Fenwick tree can be maintained to speed up the computation.

Exercises:

• AtCoder Educational DP Contest Q - Flowers
• AtCoder Educational DP Contest W - Intervals
• Codeforces 115 E. Linear Kingdom Races

CDQ divide-and-conquer optimization of DP

Main page: CDQ Divide-and-Conquer Optimization of DP

As in the previous section, view the entire DP process as a series of query and update operations. For some problems, computing them in order is too complex, so the entire query and update process can be taken offline and accelerated using CDQ divide and conquer.

CDQ divide-and-conquer optimization of DP is also common in the following types of problems:

• Slope-optimization DP based on CDQ divide and conquer
• Divide-and-conquer optimization of slope-monotone DP

Binary-lifting optimization of DP

Related page: Binary Lifting

In some problems, the state $f(i)$ is set to the result obtained after making $2^i$ transitions from the initial state. This uses the idea of binary lifting to transform the original problem, and is therefore often called binary-lifting optimization of DP.

Sometimes, DP problems whose state transition equation has a form such as

$$f(i,j) = f(i-1,f(i-1,j))$$

are also called binary-lifting (optimization) DP.

Exercises:

• Luogu P1081 [NOIP 2012 Advanced Group] Driving Trip
• Luogu P1613 Road
• Luogu P4739 [CERC2017] Donut Drone

Optimizing with problem structure

Many dynamic programming problems have structural properties such as convexity and monotonicity. Making proper use of these properties can lead to a fast solution.

Slope-optimization DP

Main page: Slope Optimization

Similar to the optimization methods introduced in the previous section, convexity of the problem can be used to maintain a convex hull and accelerate a single transition.

Quadrangle-inequality optimization of DP

Main page: Quadrangle-Inequality Optimization

DP problems involving functions that satisfy the quadrangle inequality often satisfy some form of decision monotonicity. Making use of this property, there are many specialized methods that can reduce the computational complexity. Common problem types include one-dimensional decision monotonicity problems, interval partition problems, and interval merging problems.

Slope Trick optimization of DP

Main page: Slope Trick

In some problems, it is easier to maintain the difference of the state function (that is, its slope) during state transitions. This optimization also often requires the problem to have convexity.

WQS binary search/convex optimization of DP

Main page: WQS Binary Search

For optimization DP problems with a cardinality constraint, if the problem is easier to solve without considering the cardinality constraint and the optimal value is a convex function of that constraint, the WQS binary-search method can be used to simplify the computation.

Optimizing with mathematical methods

The transitions of many dynamic programming problems can be accelerated using mathematical tools.

Matrix-exponentiation optimization of DP

Related page: Fast Exponentiation

If the state transition equation of a DP problem can be written in an autonomous form

$$f(i) = F(f(i-1)),$$

that is, the current state $f(i)$ depends only on the previous state $f(i-1)$ and not on any other input, fast exponentiation can be used directly to accelerate the computation:

$$f(n) = F^n(f(0))$$

to obtain the final answer. Since a single operation $F$ can often be written in matrix form, this optimization method is often called matrix-exponentiation optimization of DP. In fact, any transformation satisfying associativity (that is, any element in a monoid) can use this method for acceleration.

Exercises:

• Luogu P1397 [NOI2013] Matrix Game
• Luogu P3176 [HAOI2015] Splitting a Number String
• Codeforces 576 D. Flights for Regular Customers
• Luogu P6772 [NOI2020] Foodie

FFT optimization of DP

Related page: FFT

If the state transition equation of a DP problem has the form of a convolution, FFT can be considered to accelerate the transition. Of course, depending on the specific problem, other polynomial techniques may also be used.

Exercises:

• Codeforces 553 E. Kyoya and Train
• Codeforces 1784 D. Wooden Spoon

Lagrange-interpolation optimization of DP

Related page: Lagrange Interpolation

In some DP problems, the state function $f(i,j)$ is a degree-$k$ polynomial function of $j$. In this case, we can directly compute its values at $k+1$ points and use Lagrange interpolation to obtain the expression for $f(i,\cdot)$, thereby optimizing the transition or even obtaining the answer directly.

Exercises:

• Luogu P5223 Function
• Luogu P4463 [Training Team Test 2012] calc
• Luogu P5469 [NOI2019] Robot

Optimizing by simplifying the state

In addition to optimizing transitions, computational complexity can also be reduced by simplifying the state.

DP on DP and DFA minimization

Main pages: DP on DP, DFA Minimization

The state function of some DP problems can be written as $f(i,x)$, but the transition of $x$ itself is relatively complex and may even depend on another DP problem. For such problems, we can first construct an automaton for the transition of state $x$, reduce the number of states using DFA minimization, and then perform the outer DP.

State-design optimization of DP

Main page: State-Design Optimization

Some special problems can greatly reduce the number of states through clever state design.

Further reading

• A miscellany of DP optimization methods by Alex Wei