Dynamic Programming21 sections · 916 units
Open in Course

Piecewise Linear Functions

Shape of costs

Look at f(x)=x3+x7+x5f(x) = |x - 3| + |x - 7| + |x - 5|. This is continuous and piecewise linear. It has corners at x=3,5,7x = 3, 5, 7. Between corners, the slope stays constant.

At each corner, the slope increases by 22. Before x=3x = 3, all three terms contribute 1-1 each, giving slope =3= -3. Between 33 and 55, the first term flips to +1+1, so slope =1= -1. You don't need f(x)f(x) for all xx. You just need the corners and their slope increments. This insight powers Slope Trick.