When to Use Slope Trick

Use Slope Trick when:

$1.$ DP has absolute value costs $|x - a_i|$.

$2.$ The range of values is too large for standard DP.

$3.$ The DP function is convex. Other signals: reducing costs for scheduling with penalties, selecting values from ranges with deviation costs, partition problems with balance constraints. If you see $\min \sum |x_i - a_i|$ with constraints linking consecutive $x_i$, think Slope Trick. The piecewise linear shape is the giveaway.