Intro

Your DP (dynamic programming) recurrence (the formula relating states, introduced in Section 1) looks like $dp[i] = \min_j(dp[j] + a_j \cdot b_i + c_j)$. For each $i$, you check all $j$. That's $O(n^2)$.

But notice something: the expression $a_j \cdot b_i + c_j$ is linear in $b_i$. Each $j$ defines a line. You're finding the minimum among $n$ lines at point $b_i$. Most of those lines will never be optimal. I'll teach you to keep only the useful ones. By the end, you'll reduce $O(n^2)$ to $O(n)$ using the Convex Hull Trick (I'll explain why it's called "convex" in Unit 5).