一、分治算法（Divide and Conquer）

概念：

分治算法是將一個復雜問題分成若干個子問題，每個子問題結構與原問題類似，然后遞歸地解決這些子問題，最后將子問題的結果合并得到原問題的解。

特點：

• 將大問題遞歸分解成小問題。
• 子問題之間通常 相互獨立。
• 最終通過合并操作構造原問題的解。

典型場景：

• 快速排序（Quick Sort）
• 歸并排序（Merge Sort）
• 最大子數組和（Divide and Conquer 解法）

Java 示例（歸并排序）：

public class MergeSort {public static void mergeSort(int[] arr, int left, int right) {if (left >= right) return;int mid = (left + right) / 2;mergeSort(arr, left, mid);mergeSort(arr, mid + 1, right);merge(arr, left, mid, right);}private static void merge(int[] arr, int left, int mid, int right) {int[] temp = new int[right - left + 1];int i = left, j = mid + 1, k = 0;while (i <= mid && j <= right) {temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];}while (i <= mid) temp[k++] = arr[i++];while (j <= right) temp[k++] = arr[j++];for (int m = 0; m < temp.length; m++) {arr[left + m] = temp[m];}}
}

---

二、動態規劃（Dynamic Programming）

概念：

動態規劃通過將問題分解為子問題，記錄已解決的子問題的解（通常用數組或表格存儲），避免重復計算，從而提高效率。

特點：

• 子問題之間存在 重疊子問題（Overlapping Subproblems）。
• 存在 最優子結構（Optimal Substructure）。
• 使用 記憶化搜索 或 自底向上表格法。

典型場景：

• 斐波那契數列
• 背包問題
• 最長公共子序列（LCS）

Java 示例（斐波那契數列）：

public class FibonacciDP {public static int fibonacci(int n) {if (n <= 1) return n;int[] dp = new int[n + 1];dp[0] = 0; dp[1] = 1;for (int i = 2; i <= n; i++) {dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];}
}

---

三、回溯算法（Backtracking）

概念：

回溯是一種試探性方法，逐步構造問題的解，如果發現當前步驟不能得到正確解，就 回退（Backtrack） 到上一步重新嘗試。

特點：

• 適用于組合、排列、子集等枚舉類問題。
• 類似深度優先搜索（DFS），關鍵在于剪枝（優化性能）。

典型場景：

• 八皇后問題
• 子集生成、全排列
• 數獨求解

Java 示例（全排列）：

import java.util.*;public class Permutations {public static List<List<Integer>> permute(int[] nums) {List<List<Integer>> result = new ArrayList<>();backtrack(nums, new boolean[nums.length], new ArrayList<>(), result);return result;}private static void backtrack(int[] nums, boolean[] used, List<Integer> temp, List<List<Integer>> result) {if (temp.size() == nums.length) {result.add(new ArrayList<>(temp));return;}for (int i = 0; i < nums.length; i++) {if (used[i]) continue;used[i] = true;temp.add(nums[i]);backtrack(nums, used, temp, result);temp.remove(temp.size() - 1);used[i] = false;}}
}

---

四、三者的聯系與區別

特性/算法	分治（Divide & Conquer）	動態規劃（DP）	回溯（Backtracking）
子問題獨立	是	否（有重疊子問題）	否
解空間結構	樹（遞歸分解）	網格/圖結構	樹（搜索樹）
是否剪枝	否	是（通過緩存）	是（通過條件剪枝）
應用場景	排序、矩陣分割、最大子數組	最優化問題、序列問題	組合問題、數獨、圖遍歷等
解法策略	遞歸 + 合并	遞歸 + 記憶/狀態轉移	DFS + 回退 + 剪枝

---

總結：

• 分治適合問題可以被拆解為若干 獨立 子問題的情形；
• 動態規劃適合問題具有 重疊子問題和最優子結構；
• 回溯適合在解空間中試探性地尋找滿足條件的所有解，適合 搜索類問題。