分治動態規劃優化（divide-and-conquer DP optimization）
有些動態規劃的轉移形如 dp[i][j] = 在 k < j 上取 dp[i-1][k] + cost(k, j) 的最小值：要算第 i 層在位置 j 的值，你要在分割點 k 上搜尋。樸素地做，為每個 (i, j) 找最佳 k 要掃過所有候選，每個項 O(n)、整體 O(層數 乘以 n^2)。分治動態規劃優化是一種加速法，適用於最佳分割點具單調性時——隨著 j 增大，最佳 k 從不往回走——它把內層搜尋的 n 因子削成 log n 因子。
令 opt(j) 為（固定一層中）第 j 欄的最佳分割點 k。你需要的性質是單調性：opt(j) 對 j 非遞減。當它成立時，你用分治遞迴來計算這一層。要在已知最佳 k 落於 [optL, optR] 的前提下填一塊欄位 [lo, hi]，取中間欄 mid，只掃描範圍 [optL, optR] 來找它的最佳 k，記下 opt(mid)。然後對左半 [lo, mid-1] 以候選範圍 [optL, opt(mid)] 遞迴、對右半 [mid+1, hi] 以 [opt(mid), optR] 遞迴。因為最佳值單調，左邊欄位不可能需要比 opt(mid) 更大的 k，右邊欄位也不可能需要更小的，所以你合法地縮小了搜尋。遞迴的每一層在所有 mid 欄上做 O(n) 的總掃描工作，而共有 O(log n) 層，所以一層花 O(n log n) 而非 O(n^2)。
加上層數（i 索引），總計成為 O(層數 乘以 n log n)。這是與凸包優化、Knuth 優化並列的標準動態規劃加速工具之一。關鍵的誠實提醒：它只在 opt(j) 真的單調時才正確，而那個單調性本身是你必須驗證、而非假設的性質。一個常見的充分條件是 cost 滿足四邊形不等式（也正是 Knuth 優化背後的條件）。若 opt(j) 不單調，遞迴會悄悄地在某些欄上錯過真正的最佳值——它不會報錯，只是回傳錯誤答案——所以信任它之前要先證明單調性（或至少嚴格測試）。
把陣列分成 k 個連續組以最小化各組成本之和。層遞迴 dp[i][j] = 在 m 上取 dp[i-1][m] + cost(m+1, j) 的最小值，當 cost 性質良好時其最佳分割具單調性。用分治遞迴計算每一層花 O(n log n)，所以全部 k 層花 O(k n log n)，相對於樸素的 O(k n^2)。
最佳分割的單調性讓中間欄的選擇限定左右兩半的搜尋範圍。
這個優化只在最佳分割點對 j 單調時才有效（常由四邊形不等式保證）。在不具該性質時套用，它會悄悄回傳錯誤答案——它從不當機，所以務必先驗證單調性。