分治法的递归实现一. 分治思想分治法核心分、治、合分将大问题拆分为多个结构相同的子问题治递归求解子问题子问题足够小时直接返回递归出口合合并子问题的解得到原问题结果二. C通用模板cpp// l、r代表区间左右边界int divide(int l, int r){// 递归出口if (l r)return 基础解;// 分int mid (l r) / 2;int leftRes divide(l, mid);int rightRes divide(mid 1, r);// 合return merge(leftRes, rightRes);}三. 示例归并排序经典分治C代码cpp#include#includeusing namespace std// 合并两个有序区间void merge(vector arr, int l, int mid, int r){vector tmp(r - l 1);int i l, j mid 1, k 0;while (i mid j r){if (arr[i] arr[j])tmp[k] arr[i];elsetmp[k] arr[j];}while (i mid) tmp[k] arr[i];while (j r) tmp[k] arr[j];// 写回原数组for (int p 0; p tmp.size(); p)arr[l p] tmp[p];}// 分治递归void mergeSort(vector arr, int l, int r){if (l r) return; // 递归终止int mid (l r) / 2;mergeSort(arr, l, mid); // 处理左半区间mergeSort(arr, mid1, r); // 处理右半区间merge(arr, l, mid, r); // 合并结果}int main(){vector arr {5,2,9,1,6};mergeSort(arr, 0, arr.size()-1);for (int num : arr)cout num ;return 0;}复杂度\boldsymbol{O(n\log n)}四. 适用场景 易错点适用归并排序、快速排序、数组求最值、统计逆序对等。易错缺少递归出口栈溢出区间划分错误元素重复或漏掉忘记合并子问题结果小结分治递归自顶向下拆分自底向上合并。把复杂大问题拆解成简单小问题求解是分治最巧妙的地方。
