獨立子問題（independent subproblems）

當你把一件工作分給同事時，唯有沒有人需要偷看別人的進度才能完成自己的部分，這種分工才會乾淨俐落。如果兩個人偷偷在編輯同一張共用的頁面，你就不能只是把工作分出去然後走開。同樣的條件決定了分治法是否合適：你切出的子問題必須是獨立的，意思是每個子問題都能各自解決，遞迴過程中兄弟子問題之間沒有資訊互相流動。

具體而言，獨立包含兩件事。第一，子問題作用在彼此分開（或至少不互相干擾）的資料上，所以解其中一個不會改變另一個所需的東西。第二——這是比較微妙的地方——遞迴在不同分支上不會重複碰到同一個子問題。在合併排序中，左半與右半是陣列中互不重疊的切片；排好一半並不會告訴你關於另一半的任何必要資訊，兩次遞迴呼叫也從不共用子問題。對比費氏數列的天真遞迴：F(n) 呼叫 F(n-1) 與 F(n-2)，但 F(n-1) 本身又呼叫 F(n-2)，於是 F(n-2) 被解了兩次——分支重疊，因此在有用的意義上它並不獨立。

這個區別正是兩大設計範式之間的分水嶺。獨立子問題意味著每個子問題沿自己的分支恰好解一次，於是像 T(n) = 2 T(n/2) + O(n) 這樣乾淨的遞迴關係式成立，分治法因而有效率。重疊子問題——同一個較小問題能用許多路徑到達——會使天真遞迴指數爆炸，解法是動態規劃，它把每個相異子問題解一次並把答案存起來。當你看到遞迴結構時，先判斷自己處於哪種情況，就是第一個關鍵決定。