Skip to content

CHT / Li Chao Ladder

This ladder is for the first DP-optimization lane where previous states become lines and current states become point queries.

Who This Is For

Use this lane if:

  • you can already derive a clean recurrence
  • the hard part is no longer "what is the state?"
  • the recurrence has become affine in one query variable

This is a thin lane on purpose:

  • one family
  • two exact starters
  • one direct in-repo DP flagship rep
  • one direct structure-verifier rep
  • strong compare points back into DP Foundations, DP cheatsheet, and lighter hull routes

Warm-Up

  • derive dp[i] = min_j(m_j x_i + b_j) cleanly
  • identify which part is slope, intercept, and query
  • check whether slope order or query order is monotone before building a Li Chao tree

Target skill:

  • explain why Monster Game I is still the same family even if it can use a lighter monotone hull

Warm-up compare points:

Core

Target skill:

  • know when generic online insertion + query order wants LineContainer, when bounded-domain midpoint recursion wants Li Chao, and when a deque hull is still lighter

Stretch

Target skill:

  • distinguish "full-domain line container" from "segment Li Chao" and "monotone hull"

Retrieval Layer

Repo Anchors And Compare Points

The cleanest in-repo loop here is:

  1. derive the line transformation from the Convex Hull Trick / Li Chao Tree topic
  2. trust one exact implementation through Monster Game II or Line Add Get Min
  3. compare it back against Monster Game I so the chooser between monotone hull, LineContainer, and Li Chao becomes real

Exit Criteria

You are ready to move on when:

  • you can derive m, b, and x cleanly from the recurrence
  • you can say when monotone hull is enough, when LineContainer fits, and when Li Chao is safer
  • you can explain why a Li Chao node stores the line that wins at its midpoint
  • you can explain why a LineContainer line owns one breakpoint interval on the lower envelope

External Practice