贪心、回溯、动态规划、分治算法的区别（附Java代码）_贪心回溯动态规划区别
文章目录
- 前言
- 一、贪心算法 (Greedy Algorithm)
-
- 思想
- 适用场景
- 优点
- 缺点
- 示例代码
- 二、回溯算法 (Backtracking)
-
- 思想
- 适用场景
- 优点
- 缺点
- 示例代码
- 三、动态规划 (Dynamic Programming)
-
- 思想
- 适用场景
- 优点
- 缺点
- 示例代码
- 四、分治算法 (Divide and Conquer)
-
- 思想
- 适用场景
- 优点
- 缺点
- 示例代码
- 如何快速区分使用哪种算法？
前言
贪心、回溯、动态规划、分治算法都是常见的算法思想，主要区别在于它们解决问题的方式和适用的场景
一、贪心算法 (Greedy Algorithm)
思想
每一步都做出局部最优选择，以期最终获得全局最优解。
适用场景
问题具有贪心选择性质，即每个局部最优选择最终会导致全局最优解的产生。
优点
实现简单，效率较高。
缺点
不能保证所有问题都能得到全局最优解，通常用于有贪心性质的问题。
示例代码
找零钱问题（贪心解法）
通过贪心选择，每次选取能减少金额最多的硬币，最终获得最少硬币数。
import java.util.Arrays;public class GreedyChange { public static int minCoins(int[] coins, int amount) { Arrays.sort(coins); // 先排序，保证从最大面值开始 int count = 0; for (int i = coins.length - 1; i >= 0; i--) { if (amount >= coins[i]) { count += amount / coins[i]; // 用尽可能多的当前面值 amount %= coins[i]; // 更新剩余金额 } } return count; } public static void main(String[] args) { int[] coins = {1, 2, 5, 10, 20, 50}; int amount = 93; System.out.println(\"最少硬币数：\" + minCoins(coins, amount)); }}二、回溯算法 (Backtracking)
思想
尝试所有可能的解，当发现某个解不可行时，回退到上一步并尝试其他可能性。
适用场景
问题具有多层决策，每层决策依赖上一步的选择。常用于组合问题、排列问题、路径问题等。
优点
能够解决所有的可能解问题。
缺点
效率低，容易造成指数级的时间复杂度。
示例代码
N皇后问题
通过递归和回溯尝试每一行放置皇后的位置，若当前选择不可行，回溯到上一行重新选择。
public class NQueens { final int N = 8; // N表示棋盘大小 int[] board = new int[N]; // 判断某位置是否合法 boolean isValid(int row, int col) { for (int i = 0; i < row; i++) { // 检查同列和对角线冲突 if (board[i] == col || Math.abs(board[i] - col) == Math.abs(i - row)) { return false; } } return true; } // 回溯核心逻辑 boolean solve(int row) { if (row == N) { printSolution(); return true; // 找到解 } boolean hasSolution = false; for (int col = 0; col < N; col++) { if (isValid(row, col)) { board[row] = col; // 选择此列 hasSolution |= solve(row + 1); // 递归下一行 } } return hasSolution; } // 打印棋盘 void printSolution() { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (board[i] == j) { System.out.print(\"Q \"); } else { System.out.print(\". \"); } } System.out.println(); } System.out.println(); } public static void main(String[] args) { NQueens queens = new NQueens(); queens.solve(0); }}三、动态规划 (Dynamic Programming)
思想
将问题拆解为子问题，并通过存储子问题的解来避免重复计算，通常用于求解最优解。
适用场景
问题可以分解为重叠子问题，且问题具有最优子结构（即子问题的最优解可以构成整个问题的最优解）。
优点
效率高，避免了重复计算。
缺点
需要额外的存储空间，适合求解具有子问题重叠性质的问题。
示例代码
斐波那契数列（动态规划解法）
通过动态规划的方式保存之前的计算结果，从而避免了递归带来的重复计算。
public class FibonacciDP { public static int fib(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]; } public static void main(String[] args) { int n = 10; System.out.println(\"第 \" + n + \" 个斐波那契数：\" + fib(n)); }}四、分治算法 (Divide and Conquer)
思想
将问题分解为多个子问题，分别解决子问题，然后将子问题的解合并为原问题的解。
适用场景
问题可以被分成独立的子问题，且子问题的解可以合并成整体问题的解。
优点
通过递归解决子问题，减少复杂度。
缺点
某些问题无法有效分治，递归会带来额外的栈空间消耗。
示例代码
归并排序
通过递归分治的方式将数组分成若干小部分进行排序，最后合并这些部分以得到最终的有序数组。
import java.util.Arrays;public class MergeSort { // 归并排序主函数 public static void mergeSort(int[] arr, int left, int right) { if (left < right) { int mid = left + (right - left) / 2; // 分治，递归排序左右两边 mergeSort(arr, left, mid); mergeSort(arr, mid + 1, right); // 合并排序后的两个子数组 merge(arr, left, mid, right); } } // 合并两个有序子数组 public 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) { if (arr[i] <= arr[j]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; } } while (i <= mid) { temp[k++] = arr[i++]; } while (j <= right) { temp[k++] = arr[j++]; } // 将合并后的结果复制回原数组 System.arraycopy(temp, 0, arr, left, temp.length); } public static void main(String[] args) { int[] arr = {38, 27, 43, 3, 9, 82, 10}; System.out.println(\"排序前: \" + Arrays.toString(arr)); mergeSort(arr, 0, arr.length - 1); System.out.println(\"排序后: \" + Arrays.toString(arr)); }}如何快速区分使用哪种算法？
- 是否可以分治：如果问题可以分成多个独立子问题，并且每个子问题的解可以合并，那就考虑分治算法。
- 是否有重叠子问题：如果问题可以通过求解子问题来优化效率，并且子问题存在重复计算，可以考虑动态规划。
- 是否需要尝试所有可能解：如果问题要求找到所有可能的解决方案，并且可以通过回溯进行剪枝，选择回溯算法。
- 是否存在贪心选择性质：如果问题允许通过局部最优选择直接找到全局最优解，可以考虑使用贪心算法。
