You want to compute dp[1],dp[2],…,dp[n] where Base case: dp[0]=0. For i≥1: dp[i]=minj<i(dp[j]+cost(j,i)). Naively, each takes O(n) time.
D&C improvement computes the middle element first: dp[mid]. Finding opt[mid] takes O(n) time.
But now you know: for all i<mid, search only j≤opt[mid]. For all i>mid, search only j≥opt[mid]. Recurse on both halves.
Each level of recursion does O(n) total work. Picture a binary tree: at the root Compute dp[n/2], its children compute dp[n/4] and dp[3n/4]. Each level handles O(n) work total across all nodes. With O(logn) levels, total is O(nlogn).
