This article summarizes some Optimization Techniques for Dynamic Programming Problems

1.Prerequisite Knowledge

$tD/eD$ Problem: Problems with t dimensions of states and e dimensions of decisions. Time complexity is $O(n^{e+t})$.
Quadrilateral Inequality:

The cost function $w$ is said to satisfy the convex quadrilateral inequality when $w(a,c)+w(b,d)\le w(b,c)+w(a,d),\ a < b < c < d$ As illustrated below, the sum of $w$ over intervals 1 and 2 is less than or equal to the sum over intervals 3 and 4

\[ \underbrace {\overbrace {a \to \underbrace{b \to c}_3}^1 \to d }_4 \llap{\overbrace {\phantom{b\to c\to d}}^2}\]

Convex Complete Monotonicity：

A matrix $A$ is convex complete monotonic if： $A(a,c)\ge A(b,c)\Rightarrow A(a,d)\ge A(b,d),\ a < b < c < d$

As shown below, if the condition holds that $w$ in interval 1 is greater than in interval 2, then it can be deduced that 3 is greater than 4.

\[ \overbrace {\overbrace {a \to b \to c}^1 \to d }^3 \llap{\underbrace {\underbrace{\phantom{b\to c}}_2\phantom{\to d}}_4}\]

The convex quadrilateral inequality implies total monotonicity, but the reverse may not be true.

Interval Inclusion Monotonicity：$w$ satisfies $w(b,c)\le w(a,d),a\le b\le c\le d$
Decision Monotonicity：$r_j$ is the row index that minimizes the j-th column of matrix $A$. If $A$ satisfies convex total monotonicity, it can be deduced that $r_1 \leq r_2 \leq \cdots \leq r_m$, meaning that the row indices of the minimum values increase monotonically.

2. Optimization Methods

1. Utilizing Decision Monotonicity

Recurrence equation: $f(j) = \min_{i < j}{f(i) + w(i, j)}$

Let $A(i, j) = f(i) + w(i, j)$ represent the result of transitioning from the $i$-th row in the previous column to the $j$-th column.

If $w$ satisfies the Convex Quadrilateral Inequality $\Rightarrow$ $w$ is convex-monotonic $\Rightarrow$ $A$ is convex-monotonic $\Rightarrow$ decision monotonicity.

Define $d(j)$ as the minimum column index where the $j$-th row is better than the previous rows.

Each decision (row) has a range of connected and increasing column intervals. $d(j)$ denotes the starting point of the interval for $j$, e.g., $111224444$, $d(1) = 1$, $d(2) = 4$, $d(4) = 6$.

Since decision monotonicity holds, we maintain a stack $< d(j), j >$. The steps are as follows:

Binary search to find the column interval where $d(j)$ is located, pop subsequent intervals.
Perform binary search within this interval to calculate $d(j)$.
Push onto the stack.

This optimization reduces the complexity from $O(n^2)$ to $O(n\log_2n)$.

2. Divide and Conquer Optimization

Recurrence equation: $f(i, j) = \min {f(i-1, k-1) + w(k, j)}$

Also based on decision monotonicity.

Define $d(i, j)$ as the optimal decision for $f(i, j)$.

$d(i, j') \leq d(i, j), j' < j$

In the $solve(opt_L, opt_R, l, r)$ process, we traverse from $opt_L$ to $opt_R$ to calculate $d(i, m)$ at the midpoint $m = (l+r)/2$.

For $l \leq x < m$, $d(i, x)$ must be in the $[opt_L, d(i, m)]$ interval, and for $m < x \leq r$, $d(i, x)$ must be in the $[d(i, m), opt_R]$ interval. Recursive calls are made accordingly.

solve(optL,d[i][m],l,m-1);
solve(d[i][m],optR,m+1,r);

3. Monotonic Queue

Recurrence equation: $f(i) = \min_{j=b[i]}^{i-1}{g(j)} + w(i)$, where $b[i]$ increases with $i$.

If a later decision is more optimal, we can discard previous decisions. Thus, a monotonic queue maintains the decision table:

Dequeue from the front until the front satisfies the range condition.
The front becomes the optimal decision.
If the calculated $g(x)$ is better than the back, dequeue until $g(x)$ is no longer better and then enqueue.
$O(n)$ complexity.

4. Slope Optimization

Recurrence equation: $f(i) = \min{a_{i}\cdot x_{j} + b_{i} \cdot y_{j}}$

We consider each decision as a point $(x_j, y_j)$ plotted in a Cartesian coordinate system. Therefore, what we aim to find is the point that minimizes $z=a_{i}\cdot x+ b_{i} \cdot y$, Rearranging the equation, we get $y=-\frac {a_i}{b_i} \cdot x+\frac z {b_i}$. In other words, we are searching for a point where, when a line with a slope of $-\frac {a_i} {b_i}$ passes through it, the vertical intercept is minimized.

The optimal decision points are observed to lie on a convex hull.

If both the slope and $x$ are monotonic, a monotonic queue can be used for maintenance. Deleting from the queue's tail is necessary to preserve convexity, and deleting from the front is because decision points on the convex hull move monotonically. The current front is not the optimal solution, and it will not be in the future. This approach has a time complexity of $O(n)$
Otherwise, binary search can identify the optimal decision point. Connecting the points on the convex hull with edges, where the slope is monotonically increasing, when decision $i$ is inserted, first binary search to find the insertion point based on $x$. Then, perform Graham's scan on both sides to maintain convexity, i.e., deleting points. If $x$ is not monotonic, a balanced tree is needed to dynamically maintain the convex hull. This approach has a time complexity of $O(n\log_2n)$.
Alternatively, CDQ divide and conquer can be used instead of a balanced tree.
Problems involving slope optimization can generally also be solved using divide and conquer optimization.

Related post： bzoj1492 [NOI2007]货币兑换Cash

5. Convex Hull Trick

Recurrence equation: $f(i) = \min {f(j) + b_j \cdot a_i}$

Actually, it is equivalent to the equation $a_i=1, x_j=f(j), y_j=b_j, b_i=a_i$, and therefore, it can also be solved using slope optimization.

Considering each decision $A(i, j) = \color{blue}{b_j} \cdot a_i + \color{green}{f(j)}$ as a line $y = \color{blue}{m_j} \cdot x + \color{green}{c_j}$, the current optimal decision is found by substituting $x=a_i$ into all lines and determining the line with the minimum value.

We maintain effective (potentially optimal) lines using a stack.

If $b_j$ is decreasing, it is equivalent to continuously adding lines with smaller slopes. If the intersection point of the new line with the last line $l_1$ has a smaller abscissa than that of $l_1$ and $l_2$, then $l_1$ becomes invalid, and it is popped from the stack. This process is repeated until the abscissa is no longer smaller or only the stack bottom remains. At this point, the new line is pushed onto the stack. This process is similar to maintaining a convex hull.

If $a_i$ is increasing, the minimum value is always on the last line. Therefore, the complexity is $O(n)$.

6. Convex Hull Optimization 2

Transition equation: $f(i,j)=\min \{f(i-1,k)+b_k \cdot a_j\}$

With i fixed, each decision $A(j,k)=\color{blue}{b_k} \cdot a_j+\color{green}{f(i-1,k)}$, serves as a line $y=\color{blue}{m_k} \cdot x+\color{green}{c_k}$, as explained above. Therefore, the overall complexity is $O(kn)$.

7. Knuth Optimization

Transition equation: $f(i,j)=\min\{f(i,k-1)+f(k,j)\}+w(i,j)$

If $w$ satisfies the quadrilateral inequality and the interval inclusion monotonicity, then $f$ also satisfies the quadrilateral inequality.
Define the decision achieving the optimal value for $f$ as $s(i, j)$. If $f$ satisfies the quadrilateral inequality, then $s$ is monotonic: $s(i, j-1) \le s(i, j) \le s(i+1, j)$.

Therefore, the transition equation is rewritten as:

$$ f(i, j) = \min \{ f(i, k-1) + f(k, j)\} + w(i, j), \quad s(i, j-1) \le k \le s(i+1, j)$$

Since this transition equation enumerates interval lengths $L$, assuming we seek $f(i, i+L)$, and the sum of lengths in each iteration is

\[ \begin{aligned} &\sum_{i=1}^{n-L}{s(i+1,i+L)-s(i,i+L-1)}\\ &=s(2,L+1)-s(1,L)+s(3,L+2)-s(2,L+1)+s(4,L+3)-s(3,L+2)..\\ &=s(n-L+1,n)-s(1,L)\le n-1 \end{aligned}\]

Enumerating $L$ takes $O(n)$ time, thus the overall complexity is $O(n^2)$.

This optimization technique was proposed by Donald E. Knuth in the context of optimal binary search tree data structures.

3. Problems

Convex Hull Optimization（CHT）

Knuth Optimization

Divide and Conquer Optimization

Slope Optimization

BZOJ 1597 [Usaco2008 Mar]土地购买
BZOJ 3675 [APIO 2014]序列分割
BZOJ 1010 [HNOI2008]玩具装箱toy
BZOJ 3437 小P的牧场
BZOJ 3156 防御准备
BZOJ 1096 [ZJOI2007]仓库建设
BZOJ 1911 APIO 2010 Commando
BZOJ 4518 [SDOI2016] 征途
HDU 3507
HDU 3401
HDU 2191
HDU 5956 The Elder

Maintaining a dynamic convex hull using a balanced tree.

cf70d
BZOJ 2300(HAOI2011)防线修建
BZOJ 1492 货币兑换Cash
HDU 5127 Dogs’ Candies

Dynamic programming with convexity, concavity and sparsity
《算法艺术与信息学竞赛》p149。
1D1D动态规划优化初步
动态规划算法的优化技巧-毛子青
dp优化-个人对dp优化的理解
Dynamic Programming Optimizations
斜率优化二

(From a previous blog post, I don't remember the exact date of the last update.)