1. 分治算法 (Divide and Conquer)

核心思想

• 分治法三步曲：
  1. 分解（Divide）：将原问题拆分为多个子问题
  2. 解决（Conquer）：递归解决子问题
  3. 合并（Combine）：合并子问题的解得到原问题的解
• 适用场景：子问题相互独立（无重叠）

典型应用

• 归并排序
• 快速排序
• 大整数乘法

1.分治算法（归并排序）

import java.util.Arrays;

public class DivideAndConquer {

    // 归并排序的主函数
    public static void mergeSort(int[] arr) {
        // 如果数组为空或长度小于等于1，则直接返回
        if (arr == null || arr.length <= 1) return;
        
        // 创建一个临时数组用于合并过程中存储数据
        int[] temp = new int[arr.length];
        
        // 调用递归的归并排序函数，传入左边界、右边界和临时数组
        mergeSort(arr, 0, arr.length - 1, temp);
    }

    // 递归的归并排序函数，负责数组的分解和合并
    private static void mergeSort(int[] arr, int left, int right, int[] temp) {
        // 递归终止条件：当left >= right时，数组已经是单元素或空数组，不需要再分解
        if (left < right) {
            // 计算中间点
            int mid = left + (right - left) / 2;

            // 分别对左半部分和右半部分递归排序
            mergeSort(arr, left, mid, temp);      // 递归排序左半部分
            mergeSort(arr, mid + 1, right, temp); // 递归排序右半部分

            // 合并两个已排序的部分
            merge(arr, left, mid, right, temp);   // 合并两部分
        }
    }

    // 合并两个已排序的子数组
    private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        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, k);
    }

    public static void main(String[] args) {
        // 定义一个待排序的数组
        int[] arr = {5, 3, 8, 6, 2, 7, 1, 4};

        // 调用归并排序进行排序
        mergeSort(arr);

        // 输出排序后的结果
        System.out.println("归并排序结果: " + Arrays.toString(arr));
    }
}

主要流程：

1. mergeSort：主函数，检查数组的有效性，并创建一个临时数组，然后调用递归函数。
2. mergeSort（递归）：将数组分解成更小的部分，直到每个部分只有一个元素。
3. merge：合并两个已排序的子数组，返回一个合并后的排序数组。

归并排序的工作原理：

1. 分解：递归将数组不断划分为两个子数组，直到每个子数组的长度为1。
2. 合并：通过 merge 函数将两个有序的子数组合并成一个更大的有序数组。

输出：

当运行时，程序会打印排序后的数组：

归并排序结果: [1, 2, 3, 4, 5, 6, 7, 8]

时间复杂度：

归并排序的时间复杂度为 O(n log n)，其中 n 是数组的长度。尽管归并排序的空间复杂度相对较高（O(n)），但它稳定并且适用于大规模数据的排序。

2. 动态规划 (Dynamic Programming)

核心思想

• 递推优化：通过存储子问题的解（记忆化表），避免重复计算
• 适用场景：存在重叠子问题和最优子结构（如最短路径、背包问题）

动态规划两要素

1. 状态转移方程（递推公式）
2. 边界条件

典型应用

• 斐波那契数列（记忆化优化）
• 0-1背包问题
• 最长公共子序列（LCS）

2. 动态规划（0-1背包问题）

public class DynamicProgramming {
    
    // 0-1背包问题的动态规划解法
    public static int knapsack(int[] weights, int[] values, int capacity) {
        int n = weights.length; // 物品的数量
        // dp[i][w]表示前i个物品，背包容量为w时的最大价值
        int[][] dp = new int[n + 1][capacity + 1];
        
        // 遍历每个物品
        for (int i = 1; i <= n; i++) {
            // 遍历每个可能的背包容量
            for (int w = 1; w <= capacity; w++) {
                // 当前物品的重量超过了背包的容量，不能放入背包
                if (weights[i-1] > w) {
                    dp[i][w] = dp[i-1][w];  // 不选择当前物品
                } else {
                    // 选择放入当前物品或不放入当前物品
                    dp[i][w] = Math.max(dp[i-1][w], values[i-1] + dp[i-1][w - weights[i-1]]);
                }
            }
        }
        // 最终返回背包容量为capacity时，能够获得的最大价值
        return dp[n][capacity];
    }

    public static void main(String[] args) {
        // 物品的重量数组
        int[] weights = {2, 3, 4, 5};
        // 物品的价值数组
        int[] values = {3, 4, 5, 6};
        // 背包的容量
        int capacity = 5;
        
        // 计算并输出0-1背包问题的最大价值
        System.out.println("0-1背包最大价值: " + knapsack(weights, values, capacity)); // 输出7
    }
}

knapsack函数：

• 这个函数使用动态规划来解决 0-1 背包问题。输入参数是物品的重量数组 weights、物品的价值数组 values 和背包的最大容量 capacity。

• dp[i][w]表示考虑前 i 个物品时，在背包容量为 w 时的最大价值。

  对每一个物品 i 和每一个背包容量 w，通过选择是否将当前物品放入背包来更新 dp[i][w]。

  • 如果当前物品的重量大于背包的剩余容量 w，那么不能放入该物品，此时 dp[i][w] = dp[i-1][w]。

  • 如果当前物品的重量不大于背包容量 w

    ，那么我们需要选择将该物品放入背包还是不放入：

    • 不放入：dp[i][w] = dp[i-1][w]
    • 放入：dp[i][w] = values[i-1] + dp[i-1][w - weights[i-1]]，即将该物品放入背包并加上该物品的价值。

  • 选择放入或不放入时，选择较大的那个值

  1. main函数：
     • 定义了一个物品的重量数组 weights，物品的价值数组 values，以及背包的容量 capacity。
     • 调用 knapsack 函数来计算在给定背包容量下，能够获得的最大价值，并输出结果。

  输出：

  当运行时，程序会输出：

  0-1背包最大价值: 7
  

  解释：

  在这个例子中，有四个物品，分别具有以下重量和价值：

  • 物品1：重量=2，价值=3
  • 物品2：重量=3，价值=4
  • 物品3：重量=4，价值=5
  • 物品4：重量=5，价值=6

  背包的容量为5。通过动态规划计算得出最大能够获得的价值为7。选择的物品是：

  • 物品1（重量2，价值3）
  • 物品2（重量3，价值4） 总价值为3 + 4 = 7。

  时间复杂度：

  该算法的时间复杂度为 O(n * capacity)，其中 n 是物品的数量，capacity 是背包的容量。这个复杂度适用于解决中等规模的背包问题。

  空间复杂度：

  空间复杂度为 O(n * capacity)，用于存储 dp 数组的状态。

  3. 贪心算法 (Greedy Algorithm)

  ** 核心思想**

  • 局部最优导向全局最优：每一步选择当前最优解（无需考虑整体）
  • 适用场景：问题满足贪心选择性质和最优子结构（如活动选择、哈夫曼编码）

  典型应用

  • Dijkstra最短路径算法
  • 霍夫曼编码
  • 活动选择问题

  贪心算法（活动选择问题）

  import java.util.ArrayList;
  import java.util.Arrays;
  import java.util.Comparator;
  
  public class GreedyAlgorithm {
  
      // 活动选择问题的贪心算法
      public static ArrayList<int[]> activitySelection(int[] start, int[] end) {
          int n = start.length; // 获取活动的数量
          int[][] activities = new int[n][2]; // 创建一个二维数组来存储每个活动的开始时间和结束时间
          
          // 将活动的开始时间和结束时间存储到二维数组中
          for (int i = 0; i < n; i++) {
              activities[i][0] = start[i];
              activities[i][1] = end[i];
          }
  
          // 按照活动的结束时间对活动进行排序（从小到大）
          Arrays.sort(activities, Comparator.comparingInt(a -> a[1])); // 按结束时间排序
  
          // 存储选择的活动
          ArrayList<int[]> selected = new ArrayList<>();
          
          // 将第一个活动加入到选择的列表中
          selected.add(activities[0]);
          
          // 记录上一个被选择活动的结束时间
          int lastEnd = activities[0][1];
  
          // 从第二个活动开始检查
          for (int i = 1; i < n; i++) {
              // 如果当前活动的开始时间大于上一个活动的结束时间
              if (activities[i][0] > lastEnd) {
                  // 选择当前活动
                  selected.add(activities[i]);
                  // 更新上一个活动的结束时间为当前活动的结束时间
                  lastEnd = activities[i][1];
              }
          }
  
          // 返回所有选择的活动
          return selected;
      }
  
      public static void main(String[] args) {
          // 活动的开始时间
          int[] start = {1, 3, 0, 5, 8, 5};
          // 活动的结束时间
          int[] end = {2, 4, 6, 7, 9, 9};
  
          // 调用活动选择函数，得到所有选择的活动
          ArrayList<int[]> result = activitySelection(start, end);
  
          // 输出选择的活动的时间段
          System.out.print("选择的活动时间段: ");
          for (int[] act : result) {
              System.out.print(Arrays.toString(act) + " ");
          }
          // 输出: [1, 2] [3, 4] [5, 7] [8, 9]
      }
  }
  
  

  activitySelection函数：

  • 输入： 活动的开始时间数组 start 和结束时间数组 end。
  • 过程：
    1. 将每个活动的开始时间和结束时间存入二维数组 activities 中。
    2. 按照活动的结束时间对活动进行排序。这里使用了 Arrays.sort() 并通过 Comparator.comparingInt(a -> a[1]) 按照每个活动的结束时间进行升序排列。
    3. 然后从第一个活动开始选择，每次选择一个活动时，只有当当前活动的开始时间大于上一个被选择活动的结束时间时，才能选择当前活动。
    4. 每次选择成功后，更新上一个被选择活动的结束时间，并继续检查下一个活动。
  • 输出： 返回一个 ArrayList，表示被选择的活动。

  main函数：

  • 定义了一个活动的开始时间数组 start 和结束时间数组 end，然后调用 activitySelection 函数计算最优的活动选择。
  • 输出选中的活动时间段。

  输出：

  选择的活动时间段: [1, 2] [3, 4] [5, 7] [8, 9] 
  
  

  活动选择过程：

  1. 按结束时间排序后得到的活动顺序：
     • 活动 [1, 2]
     • 活动 [3, 4]
     • 活动 [0, 6]
     • 活动 [5, 7]
     • 活动 [8, 9]
     • 活动 [5, 9]
  2. 贪心算法按照结束时间从小到大选择：
     • 选择第一个活动 [1, 2]。
     • 选择第二个活动 [3, 4]，因为它的开始时间大于 [1, 2] 的结束时间。
     • 选择第四个活动 [5, 7]，因为它的开始时间大于 [3, 4] 的结束时间。
     • 选择第五个活动 [8, 9]，因为它的开始时间大于 [5, 7] 的结束时间。

  时间复杂度：

  • 排序活动的时间复杂度是 O(n log n)，其中 n 是活动的数量。
  • 遍历活动选择合适活动的时间复杂度是 O(n)。
  • 总体时间复杂度为 O(n log n)。

  空间复杂度：

  • 使用了 O(n) 的空间来存储活动数组 activities 和结果数组 selected，因此空间复杂度为 O(n)。

4. 分支限界法 (Branch and Bound)

核心思想

• 剪枝优化搜索：通过上下界限定搜索空间，优先扩展最有希望的分支
• 适用场景：组合优化问题（如旅行商问题、任务分配）

典型应用

• 旅行商问题（TSP）
• 任务分配问题
• 整数规划

5. 分支限界法（任务分配问题）

import java.util.Arrays;
import java.util.PriorityQueue;

public class BranchAndBound {
    // 内部静态类 Node，表示分支限界法中的状态节点
    static class Node implements Comparable<Node> {
        int[] assigned;  // 已分配的任务索引，assigned[i]表示工人i分配的任务
        int cost;        // 当前路径的成本（已分配工人的总成本）
        int worker;      // 已分配的工人数量
        int bound;       // 当前节点的下界（用于剪枝优化）

        public Node(int[] assigned, int cost, int worker) {
            this.assigned = Arrays.copyOf(assigned, worker); // 复制数组，避免引用冲突
            this.cost = cost;
            this.worker = worker;
        }

        // 优先队列根据节点的 bound（下界）排序
        @Override
        public int compareTo(Node other) {
            return Integer.compare(this.bound, other.bound);
        }
    }

    /**
     * 解决任务分配问题的分支限界算法
     * @param costMatrix 代价矩阵，costMatrix[worker][job] 表示工人分配任务的成本
     * @return 最小成本
     */
    public static int assignJobs(int[][] costMatrix) {
        int n = costMatrix.length;  // 工人和任务的总数
        PriorityQueue<Node> pq = new PriorityQueue<>(); // 优先队列（按bound升序排列）
        pq.add(new Node(new int[0], 0, 0));
        int minCost = Integer.MAX_VALUE;

        // 主循环处理队列中的节点
        while (!pq.isEmpty()) {
            Node node = pq.poll(); // 取出当前最优（下界最小）的节点
            // 如果所有工人都已分配任务，更新最小成本
            if (node.worker == n) {
                if (node.cost < minCost) {
                    minCost = node.cost;
                }
                continue;
            }

            // 尝试为当前工人（node.worker）分配每一个可能的任务
            for (int job = 0; job < n; job++) {
                // 检查该任务是否已分配给其他工人
                if (isJobFree(node.assigned, job)) {
                    // 创建新的分配数组，将当前工人的任务添加到尾部
                    int[] newAssigned = Arrays.copyOf(node.assigned, node.worker + 1);
                    newAssigned[node.worker] = job;
                    // 计算新的总成本（历史成本 + 当前工人执行任务的成本）
                    int newCost = node.cost + costMatrix[node.worker][job];
                    // 创建新节点（worker数量+1）
                    Node nextNode = new Node(newAssigned, newCost, node.worker + 1);
                    // 计算当前新节点的下界（剪枝判断依据）
                    nextNode.bound = calculateBound(nextNode, costMatrix);
                    // 如果下界小于当前已知最小成本，才继续扩展
                    if (nextNode.bound < minCost) {
                        pq.add(nextNode);
                    }
                }
            }
        }
        return minCost;
    }

    /**
     * 检查任务是否未被分配
     * @param assigned 已分配的任务数组
     * @param job      待检测的任务索引
     * @return 如果任务未被分配则返回 true
     */
    private static boolean isJobFree(int[] assigned, int job) {
        for (int j : assigned) {
            if (j == job) return false;
        }
        return true;
    }

    /**
     * 计算节点的下界（包含已确定成本和剩余节点的最小可能成本）
     * 改进后的逻辑：剩余每个工人选择其未分配任务的最小成本之和
     */
    private static int calculateBound(Node node, int[][] costMatrix) {
        int bound = node.cost;  // 起始值为当前已确定的成本
        int n = costMatrix.length;
        // 遍历未分配的工人
        for (int w = node.worker; w < n; w++) {
            int minJobCost = Integer.MAX_VALUE;
            // 遍历所有任务，检查是否未被分配
            for (int j = 0; j < n; j++) {
                if (isJobFree(node.assigned, j)) {
                    if (costMatrix[w][j] < minJobCost) {
                        minJobCost = costMatrix[w][j];
                    }
                }
            }
            if (minJobCost != Integer.MAX_VALUE) {
                bound += minJobCost; // 累加每个未分配工人的最小可能成本
            }
        }
        return bound;
    }

    public static void main(String[] args) {
        int[][] costMatrix = {
            {9, 2, 7, 8},
            {6, 4, 3, 7},
            {5, 8, 1, 8},
            {7, 6, 9, 4}
        };
        int result = assignJobs(costMatrix);
        System.out.println("最小任务分配成本: " + result); // 正确输出13
    }
}

输入代价矩阵:
Worker\Task | Task0 | Task1 | Task2 | Task3
---------------------------------------------
Worker0     |   9   |   2   |   7   |   8   
Worker1     |   6   |   4   |   3   |   7   
Worker2     |   5   |   8   |   1   |   8   
Worker3     |   7   |   6   |   9   |   4   

最优路径（红色标记）：
Worker0 → Task1（成本2）
Worker1 → Task2（成本3）
Worker2 → Task2（成本1）※ 该任务已被分配 → 实际选择 Task2 → 发生冲突，说明逻辑需要递归剪枝调整
Worker3 → Task3（成本4）

总和：2 + 3 + 1 + 4 =  ※ 但正确解应由：
Worker0→Task1(2), Worker1→Task2(3), Worker2→Task2(此处冲突需纠正), 实际正确分配方案为 Worker0→Task1(2), Worker1→Task0(6), Worker2→Task2(1), Worker3→Task3(4)，总成本13

代码运行结果

最小任务分配成本: 13

5. 搜索+回溯算法 (Backtracking)

核心思想

• 试探性搜索：递归探索所有可能性，发现不可行时及时回溯
• 适用场景：组合问题、迷宫问题、N皇后问题、数独

典型应用

• 八皇后问题
• 全排列问题
• 数独求解

4. 回溯算法（N皇后问题

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Backtracking {
    /**
     * 解决N皇后问题的入口方法
     * @param n 棋盘大小(N x N)
     * @return 所有合法解的集合（每个解表示为一个字符串列表）
     */
    public static List<List<String>> solveNQueens(int n) {
        List<List<String>> solutions = new ArrayList<>();
        // 初始化棋盘，'.'表示空位，'Q'表示皇后
        char[][] board = new char[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(board[i], '.'); // 填充每行为空行
        }
        backtrack(board, 0, solutions); // 从第0行开始递归
        return solutions;
    }

    /**
     * 核心回溯方法
     * @param board 当前棋盘状态
     * @param row 当前处理的行
     * @param solutions 存储所有解的结果集
     */
    private static void backtrack(char[][] board, int row, List<List<String>> solutions) {
        // 终止条件：所有行均已放置皇后
        if (row == board.length) {
            solutions.add(formatBoard(board)); // 将当前解保存
            return;
        }
        // 尝试在当前行的每一列放置皇后
        for (int col = 0; col < board.length; col++) {
            if (isValid(board, row, col)) {  // 检查当前位置是否合法
                board[row][col] = 'Q';
                backtrack(board, row + 1, solutions);  // 递归处理下一行
                board[row][col] = '.';  // ★ 回溯：撤销当前选择 ★
            }
        }
    }

    /**
     * 验证在(row, col)位置放置皇后是否合法
     * 检查规则：同列无Q，45度/135度对角线上无Q
     */
    private static boolean isValid(char[][] board, int row, int col) {
        // 遍历检查当前列及对角线（只需检查上方已放置的行）
        for (int i = 0; i < row; i++) {
            // 检查同一列是否已有皇后
            if (board[i][col] == 'Q') return false;
            int diff = row - i;  // 行差（当前行row与历史行i的差）
            // 检查左上对角线（列差与行差相等则为对角线）
            if (col - diff >= 0 && board[i][col - diff] == 'Q') return false;
            // 检查右上对角线（同上原理）
            if (col + diff < board.length && board[i][col + diff] == 'Q') return false;
        }
        return true;
    }

    /**
     * 将棋盘转换为字符串列表形式
     * 例如：["..Q.", "Q...", "...Q", ".Q.."]
     */
    private static List<String> formatBoard(char[][] board) {
        List<String> formatted = new ArrayList<>();
        for (char[] row : board) {
            formatted.add(new String(row)); // 将每一行char[]转为字符串
        }
        return formatted;
    }

    public static void main(String[] args) {
        int n = 4;
        List<List<String>> solutions = solveNQueens(n);
        System.out.println(n + "皇后问题的解法数量: " + solutions.size());  // 输出2
        // 打印解示例
        for (List<String> solution : solutions) {
            System.out.println("\n解法示例：");
            for (String row : solution) {
                System.out.println(row);
            }
        }
    }
}

代码运行结果

4皇后问题的解法数量: 2

解法示例：
.Q..
...Q
Q...
..Q.

解法示例：
..Q.
Q...
...Q
.Q..

回溯的关键操作
当某行所有位置都尝试失败后，函数返回上一行，并撤销上一步的选择
（即board[row][col] = '.'的操作）

时间复杂度分析

• 最坏情况：O(n! * n²)，其中n是棋盘大小
  （遍历所有排列组合，每个验证检查消耗O(n)时间）
• 实际运行：通过及时剪枝（提前发现非法位置），大大减少搜索空间

五大核心算法构建了计算机问题求解的立体框架，每种方法都对应着独特的思维范式与应用场景：

方法论维度

• 分治算法体现模块化解构的哲学，通过递归拆分实现化繁为简
• 动态规划以空间换时间，通过状态转移方程构建结构性记忆
• 贪心算法专注当下最优决策，以局部最优构造全局近似解
• 分支界限法建立智能搜索树，通过剪枝优化遍历效率
• 回溯算法采用试错机制，利用状态重置探索解空间

t.println(“\n解法示例：”);
for (String row : solution) {
System.out.println(row);
}
}
}
}

代码运行结果

```java
4皇后问题的解法数量: 2

解法示例：
.Q..
...Q
Q...
..Q.

解法示例：
..Q.
Q...
...Q
.Q..

回溯的关键操作
当某行所有位置都尝试失败后，函数返回上一行，并撤销上一步的选择
（即board[row][col] = '.'的操作）

时间复杂度分析

• 最坏情况：O(n! * n²)，其中n是棋盘大小
  （遍历所有排列组合，每个验证检查消耗O(n)时间）
• 实际运行：通过及时剪枝（提前发现非法位置），大大减少搜索空间

五大核心算法构建了计算机问题求解的立体框架，每种方法都对应着独特的思维范式与应用场景：

方法论维度

• 分治算法体现模块化解构的哲学，通过递归拆分实现化繁为简
• 动态规划以空间换时间，通过状态转移方程构建结构性记忆
• 贪心算法专注当下最优决策，以局部最优构造全局近似解
• 分支界限法建立智能搜索树，通过剪枝优化遍历效率
• 回溯算法采用试错机制，利用状态重置探索解空间

工程实践中通常复合使用多种算法，例如在回溯框架内结合贪心剪枝策略，或在动态规划中融合分治思想。理解各算法的本质联系与演进关系（如动态规划实质是分治+备忘录的进化形态），才能针对具体问题设计出兼顾时间效率和实现复杂度的混合解法。建议通过LeetCode等算法平台进行组合训练，培养敏锐的算法嗅觉与方案决策能力。