在java 算法中如何 区分 A.分治 B.动态规划 C.贪心 D.回溯， 并使用案例说明
用一个清晰的表格和具体案例说明这四种算法的区别：
对比表格
| 特性 | 分治 (Divide & Conquer) | 动态规划 (Dynamic Programming) | 贪心 (Greedy) | 回溯 (Backtracking) |
|---|---|---|---|---|
| 核心思想 | 分解→解决→合并 | 记忆化存储，避免重复计算 | 局部最优→全局最优 | 试探→回溯→继续试探 |
| 子问题关系 | 相互独立 | 重叠子问题，最优子结构 | 无后效性 | 决策树遍历 |
| 解决方向 | 自顶向下（通常递归） | 自底向上或自顶向下 | 自顶向下 | 深度优先搜索 |
| 是否最优 | 不一定最优 | 保证最优解 | 不一定最优 | 能找到所有解 |
| 典型案例 | 归并排序、快速排序 | 背包问题、斐波那契 | 哈夫曼编码、Dijkstra | N皇后、全排列 |
具体案例说明
A. 分治 (Divide & Conquer)
特点：将问题分解为独立的子问题，分别解决后合并结果
// 案例：归并排序（典型的分治算法）
public class MergeSort {public void mergeSort(int[] arr, int left, int right) {if (left < right) {int mid = (left + right) / 2;// 1. 分：分解为两个子问题mergeSort(arr, left, mid);mergeSort(arr, mid + 1, right);// 2. 治：解决子问题（这里排序）// 3. 合：合并结果merge(arr, left, mid, right);}}private void merge(int[] arr, int left, int mid, int right) {// 合并两个有序数组// ...}
}
B. 动态规划 (Dynamic Programming)
特点：有重叠子问题，存储中间结果避免重复计算
// 案例：斐波那契数列（记忆化搜索）
public class Fibonacci {// 方法1：递归（效率低，大量重复计算）public int fibRecursive(int n) {if (n <= 1) return n;return fibRecursive(n - 1) + fibRecursive(n - 2); // 大量重复计算}// 方法2：动态规划（自底向上）public int fibDP(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];}// 案例2：0-1背包问题（更典型的DP）public int knapSack(int capacity, int[] weights, int[] values, int n) {int[][] dp = new int[n + 1][capacity + 1];for (int i = 1; i <= n; i++) {for (int w = 0; w <= capacity; w++) {if (weights[i - 1] <= w) {// 状态转移方程：要当前物品 vs 不要当前物品dp[i][w] = Math.max(values[i - 1] + dp[i - 1][w - weights[i - 1]],dp[i - 1][w]);} else {dp[i][w] = dp[i - 1][w];}}}return dp[n][capacity];}
}
C. 贪心 (Greedy)
特点：每一步都选择当前看起来最优的，希望得到全局最优
// 案例：找零钱问题（注意：不一定总是得到最优解）
public class CoinChange {// 贪心算法：每次选择面值最大的硬币public int greedyCoinChange(int[] coins, int amount) {Arrays.sort(coins); // 排序int count = 0;int remaining = amount;// 从大到小选择硬币for (int i = coins.length - 1; i >= 0; i--) {while (remaining >= coins[i]) {remaining -= coins[i];count++;}}return remaining == 0 ? count : -1; // 可能无解}
}// 案例2：区间调度问题（贪心能获得最优解）
public class IntervalScheduling {public int maxMeetings(int[][] intervals) {// 按结束时间排序Arrays.sort(intervals, (a, b) -> a[1] - b[1]);int count = 1;int end = intervals[0][1];// 贪心选择：每次选择结束时间最早的for (int i = 1; i < intervals.length; i++) {if (intervals[i][0] >= end) {count++;end = intervals[i][1];}}return count;}
}
D. 回溯 (Backtracking)
特点：尝试所有可能，不行就退回（回溯）
// 案例：N皇后问题
public class NQueens {List<List<String>> result = new ArrayList<>();public List<List<String>> solveNQueens(int n) {char[][] board = new char[n][n];for (char[] row : board) Arrays.fill(row, '.');backtrack(board, 0);return result;}private void backtrack(char[][] board, int row) {if (row == board.length) {// 找到一个解result.add(construct(board));return;}for (int col = 0; col < board.length; col++) {if (isValid(board, row, col)) {// 1. 做选择board[row][col] = 'Q';// 2. 进入下一层决策backtrack(board, row + 1);// 3. 撤销选择（回溯的关键）board[row][col] = '.';}}}private boolean isValid(char[][] board, int row, int col) {// 检查列、对角线是否有冲突// ...return true;}
}// 案例2：全排列问题
public class Permutations {public List<List<Integer>> permute(int[] nums) {List<List<Integer>> result = new ArrayList<>();backtrack(nums, new ArrayList<>(), result, new boolean[nums.length]);return result;}private void backtrack(int[] nums, List<Integer> path, List<List<Integer>> result, boolean[] used) {if (path.size() == nums.length) {result.add(new ArrayList<>(path));return;}for (int i = 0; i < nums.length; i++) {if (used[i]) continue;// 选择used[i] = true;path.add(nums[i]);// 递归backtrack(nums, path, result, used);// 回溯used[i] = false;path.remove(path.size() - 1);}}
}
如何快速区分？
记住这个决策流程：
-
问：是否需要尝试所有可能解？
- 是 → 回溯（找所有解/排列组合问题）
- 否 → 进入下一步
-
问：子问题是否相互独立？
- 是 → 分治（排序、归并类问题）
- 否（有重叠子问题）→ 进入下一步
-
问：能否用局部最优推导全局最优？
- 是 → 贪心（需要证明贪心选择的正确性）
- 否/不确定 → 动态规划（需要状态转移方程）
经典问题归类
- 分治：归并排序、快速排序、最近点对、Strassen矩阵乘法
- 动态规划：背包问题、最长公共子序列、编辑距离、最短路径（Bellman-Ford）
- 贪心：Dijkstra最短路径、哈夫曼编码、最小生成树（Prim/Kruskal）、区间调度
- 回溯：N皇后、数独、全排列、组合总和、图的着色
记住：实际中算法可能结合使用，如分治+动态规划、回溯+剪枝等。