Your DP (dynamic programming) recurrence (the formula relating states, introduced in Section 1) looks like . For each , you check all . That's .
But notice something: the expression is linear in . Each defines a line. You're finding the minimum among lines at point . Most of those lines will never be optimal. I'll teach you to keep only the useful ones. By the end, you'll reduce to using the Convex Hull Trick (I'll explain why it's called "convex" in Unit 5).