Halving The Decision Range

For $dp(i,j) = \min_{k \le j} { dp(i-1, k-1) + C(k,j) }$ with no condition beyond an $O(1)$ evaluation of $C$, solving the middle $j$ first bounds the decision range of both halves, giving $O(mn \log n)$ instead of $O(mn^2)$.

For $dp(i,j) = \min_{k \le j} { dp(i-1, k-1) + C(k,j) }$ with $opt(i,j) \le opt(i,j+1)$, solving the middle $j$ first bounds the decision range of both halves, giving $O(mn \log n)$ instead of $O(mn^2)$.

For $dp(i,j) = \min_{k \le j} { dp(i-1, k-1) + C(k,j) }$ with $opt(i,j) \ge opt(i,j+1)$, solving the middle $j$ first bounds the decision range of both halves, giving $O(mn \log n)$ instead of $O(mn^2)$.

For $dp(i,j) = \min_{k \le j} { dp(i-1, k-1) + C(k,j) }$ with $C$ convex in $k$, ternary searching each $j$ for its minimum bounds the decision range directly, giving $O(mn \log n)$ instead of $O(mn^2)$.