Visualizing D&C

Imagine the states $1, 2, \ldots, n$ on a line. You solve the middle one first. Its optimal split divides the search space.

Now you have two subproblems: left half of states with left portion of search space, right half with right portion. Each subproblem is independent. The tree of recursive calls has depth $\log n$. At each level, the search ranges don't overlap. That's why total work is linear per level.