Divide and conquer (以下簡稱 D&C) 是一種設計演算法的思維模式，將問題切割為兩個以上的子問題，使用相同的解決邏輯處理各子問題，所有小問題的解合併起來即為原始問題的解。
為何會稱為 D&C 也是因為整個處理過程可以分為以下三個階段:
- Divide 分解：將一個問題分解為一系列子問題 (subproblem)。
- Conquer 解決：使用相同邏輯解決各子問題，如果問題夠小，可以直接求解。
- Combine 合併：將子問題的結果合併。
在第二個階段，以相同邏輯解決子問題，很容易可以聯想到遞迴，子問題夠小時，可以直接求解，就如同定義遞迴的終止條件 (base case or bottom case) 。
何時會應用 D&C
- 母問題適合被分割為兩個以上子問題來解時，且母問題和子問題可以用相同邏輯來解，例如 merge sort 和 quick sort 。
- 用在適合以遞迴來處理的資料結構上。 適合以遞迴來處理的資料結構具有一個特性，當資料結構被切割後，資料結構仍然具有一樣的性質，例如 array, binary tree traversal 或 linked list 。
D&C Template
前面提到 D&C 適合以遞迴處理，因此就如同遞迴一樣，
- 找出遞迴關係式。
- 定義出終止條件 ，換言之，問題小到可以直接求解 。
以下以兩個 LC 題目來講解 D&C 的應用:
LC#912 Sort an Array
這一題可以用來練習 merge sort ， merge sort 是應用 D&C 來設計的 sort algorithm ，merge sort 網路上相當多文章，這邊就不再討論。
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
mergeSort (nums, 0, nums.size()-1);
return nums;
}
void mergeSort (vector<int> &nums, int left, int right) {
if (left == right)
return;
int mid = ((right-left)>>1)+left;
mergeSort (nums, left, mid);
mergeSort (nums, mid+1, right);
merge (nums, left, mid+1, right);
}
void merge (vector<int> &nums, int start,
int second_start, int end) {
int first_len = second_start-start;
int second_len = end - second_start+1;
vector<int> data1 (first_len);
vector<int> data2 (second_len);
for (int i=0; i<first_len; i++) {
data1[i] = nums[start+i];
}
for (int i=0; i< second_len; i++) {
data2[i] = nums[second_start+i];
}
int first = 0;
int second = 0;
int current = start;
while (first < first_len && second < second_len) {
if (data1[first] < data2[second]){
nums[current] = data1[first];
first++;
} else {
nums[current] = data2[second];
second++;
}
current++;
}
while (first < first_len) {
nums[current] = data1[first];
first++;
current++;
}
}
};LC#105 Construct Binary Tree from Preorder and Inorder Traversal
題目要你構建出這棵樹 ，構建 tree 一定要找出 root, left subtree 和 right subtree 。
根據 preorder 的特性，preorder vector 的第一個元素會是 tree 的 root node ，找到 root node 後，接著找出 left 和 right subtree 出來，找出 root node 在 inorder vector 的位置，其左邊就是 left subtree ，右邊是 right subtree 。
有了以上概念，可以分出 root, 左子樹和右子樹 ，但是左子樹和右子樹還需要繼續以相同的邏輯來建構剩餘的樹出來，這樣的作法就吻合 D＆C 的使用場景，原本問題是建立一棵樹，這個問題又可以切割為兩個子問題，分別是建構左子樹和建構右子樹。
這題有個可以特別提的一點，如果題目是 BST ，可以在 inorder vector 透過 binary search 找出 root ，但因為不是，使得 vector 沒有經過排序，想要搜尋的話，時間複雜度將需要到 O(n) ，碰到這個狀況，一般都會採取以空間換取時間的作法，透過一個 hash table 預先存下每個節點對應的 index ，當要尋找節點位置的 index 時，僅需 O(1) 。
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
unordered_map<int, int> record;
for (int i=0; i<inorder.size(); i++) {
record[inorder[i]] = i;
}
return buildHelper (record, preorder, inorder, 0, preorder.size()-1, 0, preorder.size()-1);
}
TreeNode* buildHelper (unordered_map<int, int>& record,
vector<int>& preorder, vector<int>& inorder,
int inarr_left, int inarr_right,
int prearr_left, int prearr_right) {
if (prearr_left > prearr_right) return nullptr;
// Take first element of preorder array as root
int root_val = preorder[prearr_left];
TreeNode* newNode = new TreeNode(root_val);
if (prearr_left == prearr_right) {
return newNode;
}
int root_index = record[root_val];
int left_subtree_size = root_index - inarr_left;
newNode->left = buildHelper (record, preorder, inorder, inarr_left, root_index-1,
prearr_left+1, prearr_left+1 + left_subtree_size-1);
newNode->right = buildHelper (record, preorder, inorder, root_index+1, inarr_right,
prearr_left+1+ left_subtree_size, prearr_right);
return newNode;
}
};以上做法可以進一步優化，其實並不需要 preorder vector 上的 index ，因為 preoder 上的順序恰巧就是我們建構的順序，pre-order 就是先拜訪 root 再拜訪左右子樹。
class Solution {
public:
int preorder_index = 0;
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
unordered_map<int, int> record;
for (int i=0; i<inorder.size(); i++) {
record[inorder[i]] = i;
}
return buildHelper (record, preorder, inorder, 0, inorder.size()-1);
}
TreeNode* buildHelper (unordered_map<int, int>& record,
vector<int>& preorder, vector<int>& inorder,
int inarr_left, int inarr_right) {
if (inarr_left > inarr_right) return nullptr;
// Take first element of preorder array as root
int root_val = preorder[preorder_index++];
TreeNode* newNode = new TreeNode(root_val);
if (inarr_left == inarr_right) {
return newNode;
}
int root_index = record[root_val];
int left_subtree_size = root_index - inarr_left;
newNode->left = buildHelper (record, preorder, inorder, inarr_left, root_index-1);
newNode->right = buildHelper (record, preorder, inorder, root_index+1, inarr_right);
return newNode;
}
};以下整理 D&C 跟各個常見演算法的差別:
D&C 和 binary search 的差別
divide and conquer 通常將問題分為 two or more sub-problems ，而不是再將它縮減為一個更小的問題，後者通常稱為 decrease and conquer ，例如 binary search 就屬於此類。
D&C 和 backtracking 差別
- D&C 問題只會有一個解，而 backtracking 問題會有多種解。舉例: D&C 用在 merge sort 問題而 backtracking 用在 N-Queen 問題。
- D&C 的每一步都是不可或缺的，而 backtracking 有些步驟未必能找到正解，會有很多的處理。
- D&C 的每一步都是清楚且事先定義好的，但是 backtracking 的每一步都是嘗試，並不知道會不會帶你找到正解。
D&C 和 DP/Greedy/Backtracking 的差別
後面三者都可以用來找出多階段決策(multiple decision process)問題的最佳解。
D&C 比較像是將問題分為多個平行子問題，如 merge sort 將一個大問題切割兩個較小的子問題; 而其他三類會將一個問題切割為多個階段的連續子問題，形成一組決策序列 (sequence) ，問題比較難被平行化解決，例如 DP 就存在最佳子結構特性: future decisions depend on eariler decisions