Skip to content

Introduction to DP Optimization

Introduction

This page lists some common dynamic programming (DP) optimization techniques. DP optimization refers to the fact that while many DP problems can easily be formulated with naive state transition equations, direct computation is often inefficient, thus requiring certain techniques to reduce time complexity.

These methods are closely related, often share similar ideas, and frequently need to be combined. Therefore, this article only provides a rough classification, focusing on introducing some fundamental ideas.

Optimization Using Common Techniques

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

There are two typical scenarios. In the first scenario, the DP problem has a state transition equation of the form:

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

Here, the computation of the current state \(f(i)\) depends on the current input \(a_i\) and the states of the entire previous sequence \(\{f(j):j < i\}\). Therefore, a data structure can be maintained, treating each computation of \(f(i)\) as a query operation. After obtaining \(f(i)\), an update operation can be performed to modify the data structure for subsequent transitions.

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

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

Here, each \(f(i,\cdot)\) is an array or other complex object. Thus, although \(f(i,\cdot)\) depends only on the previous single state, the complexity of a single transition is high and requires optimization using data structures or other techniques.

Prefix Sum Optimization for DP

Related page: Prefix Sum

If the computation of the current state depends on the sum of a segment of previous states, prefix sums can be maintained to accelerate the computation. Problems involving high-dimensional prefix sums are also known as SOS DP.

Exercises:

Monotone Queue/Stack Optimization for DP

Main page: Monotone Queue/Stack Optimization

If the current state depends on interval maximum/minimum or similar information from previous states, monotone queues or stacks can be maintained to accelerate computation.

Segment Tree/Fenwick Tree Optimization for DP

Related pages: Segment Tree, Fenwick Tree

If each state transition involves querying sums, maximums/minimums, or other information over an interval, or if a single update operation involves interval modifications, segment trees or Fenwick trees can be maintained to accelerate computation.

Exercises:

CDQ Divide and Conquer Optimization for DP

Main page: CDQ Divide and Conquer Optimization for DP

Similar to the previous section, the entire DP process can be viewed as a series of query and update operations. For some problems, sequential computation is too costly. The entire query and update process can be performed offline, using CDQ divide and conquer to accelerate computation.

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

Binary Lifting Optimization for DP

Related page: Binary Lifting

In some problems, the state \(f(i)\) can be defined as the result after \(2^i\) transitions from the initial state. This transforms the original problem using the idea of binary lifting, hence it is often called binary lifting optimization for DP.

Sometimes, DP problems with state transition equations like

\[ f(i,j) = f(i-1,f(i-1,j)) \]

are also called binary lifting (optimization) DP.

Exercises:

Optimization Using Problem Structure

Many DP problems possess structural properties such as convexity or monotonicity. Leveraging these properties appropriately can lead to efficient solutions.

Slope Optimization DP

Main page: Slope Optimization

Similar to the optimization methods introduced in the previous section, the convexity of the problem can be exploited to accelerate single transitions by maintaining a convex hull.

Quadrangle Inequality Optimization for DP

Main page: Quadrangle Inequality Optimization

DP problems where the involved functions satisfy the quadrangle inequality often exhibit certain decision monotonicity. Using this property, specialized methods can be applied to reduce computational complexity. Common problem types include 1D decision monotonicity problems, interval partitioning problems, and interval merging problems.

Slope Trick Optimization for DP

Main page: Slope Trick

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

WQS Binary Search/Convex Optimization for DP

Main page: WQS Binary Search

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

Optimization Using Mathematical Methods

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

Matrix Exponentiation Optimization for DP

Related page: Binary Exponentiation

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

\[ f(i) = F(f(i-1)), \]

meaning the current state \(f(i)\) depends only on the previous state \(f(i-1)\) and not on other inputs, then binary exponentiation can be directly applied to accelerate the computation:

\[ f(n) = F^n(f(0)) \]

to obtain the final answer. Since the single operation \(F\) can often be represented as a matrix, this optimization method is commonly called matrix exponentiation optimization for DP. In fact, any transformation satisfying associativity (i.e., any element within a monoid) can be accelerated using this method.

Exercises:

FFT Optimization for DP

Related page: FFT

If the state transition equation of a DP problem is in the form of a convolution, FFT can be considered to accelerate the transition. Depending on the specific problem, other polynomial techniques might also be used.

Exercises:

Lagrange Interpolation Optimization for DP

Related page: Lagrange Interpolation

In some DP problems, the state function \(f(i,j)\) is a polynomial function of degree \(k\) in \(j\). In this case, its values at \(k+1\) points can be computed directly, and the expression for \(f(i,\cdot)\) can be obtained via Lagrange interpolation, thereby optimizing the transition or even directly obtaining the answer.

Exercises:

Optimization by Simplifying States

Besides optimizing transitions, computational complexity can also be reduced by simplifying states.

DP of DP and DFA Minimization

Main pages: DP of DP, DFA Minimization

The state function of some DP problems can be written as \(f(i,x)\), but the transition of \(x\) itself is complex, possibly even depending on another DP problem. For such problems, an automaton can first be constructed for the transition of state \(x\), the number of states can be reduced via DFA minimization, and then the outer DP can be performed.

State Design Optimization for DP

Main page: State Design Optimization

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

Further Reading

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用