When Shapes Survive: Function Addition
You know what convex, concave, and monotonic mean. You know that the difference array stores slopes. Now here's the question that unlocks all DP optimizations:
If I add two functions together, does the sum keep the same shape?
The answer — sometimes yes, sometimes no — and knowing which is which, is the difference between an \(O(N^2)\) solution and an \(O(N \log N)\) one.
Why This Question Matters
In DP, you're almost always adding functions together. The cost of choosing item \(i\) plus the cost of everything before \(i\). The profit from this transaction plus the profit from all previous ones. The distance to this node plus the edge weight.
If both of those component functions are convex, and you can prove the sum is also convex, then the sum has a single minimum — and you can exploit that structure with binary search, convex hull trick, slope trick, or a dozen other techniques.
If you can't prove the sum keeps its shape, you're stuck with brute force.
So let's figure out the rules.
Vertical Addition: Adding Two Functions Point-by-Point
This is the common case. Two functions \(F\) and \(G\) defined on the same indices, and you create \(H(x) = F(x) + G(x)\).
The proof for all of these rules comes down to one fact: slopes add.
If \(F\) has slopes \([s_1, s_2, s_3]\) and \(G\) has slopes \([t_1, t_2, t_3]\), then \(H = F + G\) has slopes \([s_1 + t_1, \, s_2 + t_2, \, s_3 + t_3]\).
Now the rules fall out trivially:
Convex + Convex = Convex
\(F\) convex means \(s_1 \le s_2 \le s_3\) (slopes increasing). \(G\) convex means \(t_1 \le t_2 \le t_3\) (slopes increasing). Sum of slopes: \((s_1+t_1) \le (s_2+t_2) \le (s_3+t_3)\). Still increasing. Still convex. ✓
Concave + Concave = Concave
Same logic. Decreasing + decreasing = decreasing. ✓
Increasing + Increasing = Increasing
\(F\) increasing means all slopes \(\ge 0\). \(G\) increasing means all slopes \(\ge 0\). Sum of non-negatives is non-negative. ✓
Decreasing + Decreasing = Decreasing
Negative + negative = negative. ✓
Linear + Convex = Convex
A linear function has constant slopes: \([c, c, c]\). Adding a constant to each slope of a convex function doesn't change the ordering of those slopes — they're still increasing. The curve just tilts. A cup tilted sideways is still a cup. ✓
Linear + Concave = Concave
Same reasoning. Tilting a hill doesn't stop it from being a hill. ✓
The Full Table
| F | G | F + G | Why |
|---|---|---|---|
| Convex (\(\cup\)) | Convex (\(\cup\)) | Convex | Increasing slopes + increasing slopes = increasing |
| Concave (\(\cap\)) | Concave (\(\cap\)) | Concave | Decreasing + decreasing = decreasing |
| Increasing | Increasing | Increasing | Positive + positive = positive |
| Decreasing | Decreasing | Decreasing | Negative + negative = negative |
| Linear | Convex | Convex | Constant doesn't change the ordering of slopes |
| Linear | Concave | Concave | Same reason |
| Convex | Concave | ??? | No guarantee — could be anything |
| Increasing | Decreasing | ??? | No guarantee |
Those last two rows are where people get burned. Convex + concave can produce anything. You can't assume the shape survives.
Special Cases Worth Remembering
Linear Is Neutral
A straight line is simultaneously convex and concave (constant slopes are trivially both non-decreasing and non-increasing). It's the "identity element" of shape: adding it to anything preserves the original shape. This is not just trivia — it's the foundation of the Alien Trick.
Negation Flips
If \(F(x)\) is convex, then \(-F(x)\) is concave. Slopes go from increasing to decreasing.
This means: minimizing a convex function is the same problem as maximizing a concave function. They're mirror images.
Absolute Value Is Convex
The function \(|x|\) is convex — slopes go from \(-1\) to \(+1\) (increasing). Adding two absolute value functions produces another convex function. This is why "sum of absolute differences" problems often have clean optimal solutions.
Horizontal Addition: Splitting a Budget
There's a second way to "add" functions that shows up in knapsack-style problems.
Instead of \(H(x) = F(x) + G(x)\) (same \(x\) for both), you're splitting a budget \(k\) between two choices:
This is called the \((\max, +)\) convolution. You give \(i\) units to \(F\) and \(k - i\) units to \(G\), and you want the split that maximizes the total.
| F | G | Goal | Result | Complexity |
|---|---|---|---|---|
| Concave | Concave | Maximize | Concave | Mergeable in \(O(N)\) with two pointers |
| Convex | Convex | Minimize | Convex | Mergeable in \(O(N)\) — basis of Slope Trick |
| Convex | Concave | Any | Unknown | No shortcut — usually \(O(N^2)\) |
The intuition for concave + concave: both functions have diminishing returns. When you optimally split the budget, the total still has diminishing returns — because shifting a unit from the "less productive" function to the "more productive" one gives less and less benefit.
The Alien Trick: Why Convex + Linear Matters
Here's where the rules pay off in a big way.
Suppose you have a problem: "Choose exactly \(K\) transactions to maximize profit." The profit function \(P(K)\) — profit as a function of number of transactions — is concave (diminishing returns, as we saw in the stock example).
The 2D DP approach is \(O(N \cdot K)\), which is too slow. But we know that:
Concave + Linear = Concave.
So add a linear penalty: instead of maximizing \(P(K)\), maximize \(P(K) - \lambda \cdot K\) for some constant \(\lambda\). This is still concave (concave minus linear = concave plus a negated linear = still concave). And because it's concave, it has a single peak.
The trick: binary search on \(\lambda\). For each \(\lambda\), you solve the unconstrained version (no fixed \(K\), just maximize \(P - \lambda \cdot K\)). The optimal \(K\) changes as you vary \(\lambda\). Find the \(\lambda\) that gives you exactly the \(K\) you want.
The unconstrained version is a simple 1D DP — much faster. And the binary search adds only a \(\log\) factor.
That's WQS Binary Search (the Alien Trick). The entire thing rests on one rule from the table above: linear doesn't break concavity.
The 12 Optimizations Roadmap
Every major DP optimization technique exploits one of the shape rules we've covered. Here's the map — not to teach each technique (that's for dedicated pages), but to show you which rule each one depends on.
Shape Preservation Rules
| # | Technique | Rule Used | Reduces |
|---|---|---|---|
| 1 | Slope Trick | Convex + Convex = Convex | \(O(N^2) \to O(N \log N)\) |
| 2 | WQS Binary Search (Alien Trick) | Linear + Concave = Concave | \(O(NK) \to O(N \log R)\) |
| 3 | Convex Hull Trick (CHT) | Min of linear functions = convex hull | \(O(N^2) \to O(N \log N)\) or \(O(N)\) |
| 4 | D&C Optimization | Concavity (Monge) → monotone decisions | \(O(N^2 K) \to O(NK \log N)\) |
| 5 | Distance Transform | Lower envelope of parabolas | \(O(N^2) \to O(N)\) |
Structural Monotonicity
| # | Technique | Rule Used | Reduces |
|---|---|---|---|
| 6 | Min-Cost Max-Flow | Cost vs. flow is convex → greedy shortest paths | General |
| 7 | Knuth Optimization | Quadrangle inequality → bounded split points | \(O(N^3) \to O(N^2)\) |
| 8 | Ternary Search | Convex/concave = unimodal → one peak/valley | General |
| 9 | SMAWK Algorithm | Total monotonicity → row minima in \(O(N)\) | \(O(N \log N) \to O(N)\) |
Application-Specific
| # | Technique | Rule Used | Reduces |
|---|---|---|---|
| 10 | Submodularity (Project Selection) | Diminishing returns → Min-Cut | General |
| 11 | Monotonic Queue (Sliding Window) | "Newer + larger" dominates | \(O(N^2) \to O(N)\) |
| 12 | Two-Queue Huffman | Increasing + increasing = increasing | \(O(N \log N) \to O(N)\) |
The point isn't to memorize this table. It's to internalize the reflex: "My DP cost function has this shape. Which optimization does that unlock?"
The DP Framework (Session Takeaway)
Here's the practical framework from the session for building DP solutions:
- Write the brute force recurrence. Don't optimize yet.
- Look at the cost function. Is it convex? Concave? Monotonic?
- Check incremental behavior. When you go from \(i\) to \(i+1\), or from \(L\) to \(L+1\) — does the optimal decision move in one direction? That's monotonicity of the decision, which often comes from convexity/concavity of the cost.
- Match the shape to a technique. Convex cost → CHT or Slope Trick. Concave profit → WQS. Monge property → D&C. Monotone queue for bounded-window DP.
- Apply the optimization. The "how" of each technique is its own topic. But the "when" is always: check the shape first.
Cheat Sheet
Quick Reference
Vertical Addition (point-wise)
- Convex + Convex = Convex
- Concave + Concave = Concave
- Linear + Anything = Same shape as Anything
- Increasing + Increasing = Increasing
- Convex + Concave = No guarantee
Horizontal Addition (convolution)
- Concave + Concave (maximize) = Concave → \(O(N)\) merge
- Convex + Convex (minimize) = Convex → \(O(N)\) merge
Special
- \(-F\) flips convex ↔ concave
- \(|x|\) is convex
- Linear is both convex and concave
What's Next
These three pages — Seeing Numbers as Curves, Difference Arrays, and this one — give you the mathematical vocabulary for everything that follows. When you encounter a DP optimization, a graph algorithm, or a greedy technique in future sessions, the question will always come back to: "What's the shape? What does addition do to it?"
Each of the 12 optimizations in the roadmap will get its own dedicated page as we encounter them in later sessions.