Skip to main content

Divide & Conquer Optimization

Learn Divide & Conquer Optimization (Divide & Conquer, Data Structures & Algorithms) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.

Divide and Conquer DP Optimization Some dynamic programming recurrences have the form dp[g][j] = min over k < j of ( dp[g-1][k] + cost(k, j) ) . Trying every k makes each layer O(n²) . If the best split point opt(j) never moves left as j grows ( monotone optimum , true when cost satisfies the quadrangle inequality), compute the middle j first , find its best k, and recurse on the left and right halves with narrowed k ranges . Each layer drops to O(n log n) .

More lessons in Divide & Conquer