Aliens Trick — Lowering a Slope-(−λ) Line to Tangency on the Convex opt(k) Curve

Binary-search the per-item penalty λ until the tangent point's k equals the target k, then recover opt(k) = f(λ) − λ·k.

λ=50

Convex opt(k) curve  ·  tangent line of slope −λ

opt(k) point tangent point (cnt(λ)) target k line slope −λ lower hull

Binary search on λ

lo = 0 hi = 100 mid = –
λ = –, cnt(λ) = –, target k = 3
f(λ) = –
decision: press Run or Step

Recovery

opt(k) = f(λ) − λ·k = –
true opt(k) = –

Complexity

StepCost
One penalized DP f(λ)O(DP_cost)
Binary search on λO(log range)
Aliens totalO(log range · DP_cost)
Naive (count dimension)O(k · DP_cost)
Recovery f(λ) − λ·kO(1)

Probe log