分治法 Divide and Conquer
1.分治法
分治法（Divide and Conquer）是一种常见的算法设计思想，它将一个大问题分解成若干个子问题，递归地解决每个子问题，最后将子问题的解合并起来得到整个问题的解。分治法通常包含三个步骤：
- 1. Divide：将问题分解成若干个子问题。
- 2. Conquer：递归地解决每个子问题。
- 3. Combine：将子问题的解合并起来得到整个问题的解。
分治法的主要思想是将问题分解成若干个相互独立的子问题，通过递归地解决每个子问题，最后将子问题的解合并起来得到整个问题的解。这种思想可以应用于许多问题的解法中，如排序、搜索、图论、数学计算等等。
一些常见的使用分治法的算法包括：归并排序、快速排序、二分搜索、线性时间选择、Karatsuba 算法等等。
2.练习题
1）
力扣
https://leetcode.cn/problems/different-ways-to-add-parentheses/解题思路：
依次遍历字符串的每个字符，如果是运算符，就递归计算左边和右边的值。
class Solution {
public:vector<int> diffWaysToCompute(string expression) {int n = expression.size();vector<int> res;for(int i=0;i<n;i++){char c = expression[i];if(c=='+'||c=='-'||c=='*'){vector<int> left = diffWaysToCompute(expression.substr(0,i));vector<int> right = diffWaysToCompute(expression.substr(i+1));for(auto l:left){for(auto r:right){switch(c){case '+': res.push_back(l+r);break;case '-': res.push_back(l-r);break;case '*': res.push_back(l*r);break;}}}}}if(res.empty()) res.push_back(stoi(expression));return res;}};2)
力扣https://leetcode.cn/problems/beautiful-array/description/
解题思路：
首先确定一点，怎么满足这个条件：
- 对于每个
0 <= i < j < n，均不存在下标k（i < k < j）使得2 * nums[k] == nums[i] + nums[j]。
最简单的方法就是让右边的nums[i] + nums[j] 这个表达式的值为奇数，因为2 * nums[k]肯定是偶数。这样我们可以假设i<j，且nums[i]为奇数，nums[j]为偶数。也就是让数组左边为奇数，右边为偶数。
又因为如果A是漂亮数组，那么a*A+b还是漂亮数组。
所有我们可以用分治法，将问题从大到小拆解，先满足每个长度为1、2、3......的数组都是漂亮数组，这样最后长度为n的数组也是漂亮数组。
代码：
class Solution {
public:vector<int> beautifulArray(int n) {vector<int> res(n,1);part(0,n-1,res);return res;}void part(int left, int right, vector<int>& res){if(left>=right) return;int mid = left + (right-left)/2;part(left, mid, res);part(mid+1, right, res);for(int i=left;i<=mid;i++){res[i] = 2*res[i]-1;}for(int i=mid+1;i<=right;i++){res[i] = 2*res[i];}}
};