DP with Convex Hull Trick

Convex hull trick optimizes minimum queries over affine functions. The DP-specific step is discovering lines inside a recurrence. We minimize dp[i]=min over j<i of dp[j]+(x[i]−x[j])²+C for strictly increasing positions. Expanding the square separates a destination term from a line contributed by each predecessor. Ordered slopes and ordered queries make a deque sufficient; other orders need a different hull structure.

Prerequisites: One-Dimensional DP; Convex Hull Trick in Advanced Algorithms; deque amortization. Related existing lessons: Convex Hull Trick.

Build the idea

1. Recognize the repeated subproblems

   The direct algorithm has n position states and n predecessor choices, so it is quadratic. A transition that can be written destinationTerm(i)+slope(j)·query(i)+intercept(j) suggests line queries. This algebraic form is necessary for this CHT usage; an arbitrary nonlinear function of both i, j cannot be inserted as if it were a line.

2. Define the state

   x[0]=0, dp[0]=0. Predecessor j contributes line slope=−2x[j], intercept=dp[j]+x[j]². Querying at x[i] gives the minimum of those lines, then add x[i]²+C. Only j<i may be present, so compute/query before adding i’s line. The hull summarizes candidates, not polygon vertices from a geometric convex-hull lesson.

3. Derive the transition

   Strictly increasing x gives strictly decreasing inserted slopes and increasing query coordinates. For three lines a, b, c in slope order, b is redundant when its intersection with a occurs no earlier than its intersection with c. Compare those rational intersection positions by cross multiplication, not floating division. At query time, pop the front while the next line is no worse; with increasing x, the discarded line cannot become better again.

4. Base cases and computation order

   Initialize the hull with predecessor zero’s line y=0. For i=1…n, query, compute dp[i], then remove redundant back lines and append i’s line. No equal slopes occur under strict positions; general implementations must explicitly retain the best intercept among equal slopes. The program’s small integer bounds make cross-products provably fit long long, avoiding an unstated wider-integer dependency.

5. Correctness and invariant

   The expanded square is exactly the original recurrence, so a correct line minimum gives the same dp. Ordered line intersections justify back deletion; ordered queries justify permanent front deletion. Each line is appended and removed at most once per end, so total hull operations are linear. If queries arrive arbitrarily, a previously discarded front line might become useful again; the amortized deque proof would fail.

6. Work the example

   For x=[1,2,4], C=3, the dp values are 4,7,14. At x=4, the three candidates are 19 from j=0,16 from j=1, and 14 from j=2. The table lists the line form for each available predecessor and demonstrates that the best predecessor can change as queries grow.

   predecessor j	slope	intercept	line at x=4
   0	0	0	0
   1	-2	5	-3
   2	-4	11	-5

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<deque>
struct Line{
    long long slope,intercept;
    long long value(long long x)const{
        return slope*x+intercept;
    }
};
bool redundant(Line a,Line b,Line c){
    return (b.intercept-a.intercept)*(b.slope-c.slope)>=
        (c.intercept-b.intercept)*(a.slope-b.slope);
} // Descending slopes; compare consecutive intersection positions without division.
int main(){
    int n;
    long long penalty;
    std::cin>>n>>penalty;
    std::vector<long long>x(n+1),dp(n+1);
    for(int i=1;i<=n;++i){
        std::cin>>x[i];
    }
    std::deque<Line>hull{{0,0}};
    for(int i=1;i<=n;++i){
        while(hull.size()>1&&hull[1].value(x[i])<=hull[0].value(x[i])){
            hull.pop_front();
        }
        dp[i]=x[i]*x[i]+penalty+hull.front().value(x[i]);
        Line next{-2*x[i],dp[i]+x[i]*x[i]};
        while(hull.size()>1&&redundant(hull[hull.size()-2],hull.back(),next)){
            hull.pop_back();
        }
        hull.push_back(next);
    }
    std::cout<<dp[n]<<'\n';
}

Complexity analysis

Direct recurrence:O(n²) time/O(n) values. Ordered deque hull:O(n) total query/insertion work and O(n) storage. Since choosing j=0 gives dp[i]≤x[i]²+C≤1.01·10^8, intercepts≤2.01·10^8 and slope differences≤20000; redundancy products≤4.02·10^12 fit long long.

Example input and output

Read n C (0≤n≤10000,0≤C≤10^6), then strictly increasing integer positions 1≤x1<…<xn≤10000. x0=dp0=0. Print minimum DP cost for n; empty input returns zero.

Input

3 3
1 2 4

Output

14

For x=[1,2,4], C=3, the dp values are 4,7,14. At x=4, the three candidates are 19 from j=0,16 from j=1, and 14 from j=2. The table lists the line form for each available predecessor and demonstrates that the best predecessor can change as queries grow.

Practical applications

Use when recurrence algebra produces line queries. The existing Advanced Algorithms CHT and Li Chao lessons cover broader data structures; this lesson focuses on deriving lines and proving that this monotone DP instance permits the simpler deque.

Check your understanding

Which assumption permits permanent removal from the query end?

Put it into practice

Compare with every j<i transition on random increasing positions.