典型的分治算法：归并排序

void sort(int[] nums, int lo, int hi) {
    int mid = (lo + hi) / 2;
    /****** 分 ******/
    // 对数组的两部分分别排序
    sort(nums, lo, mid);
    sort(nums, mid + 1, hi);
    /****** 治 ******/
    // 合并两个排好序的子数组
    merge(nums, lo, mid, hi);
}

241. Different Ways to Add Parentheses

1、不要思考整体，而是把目光聚焦局部，只看一个运算符

2、明确递归函数的定义是什么，相信并且利用好函数的定义

考察算式 1 + 2 * 3 - 4 * 5 首先考虑只有一层括号的可能性（不嵌套

(1) + (2 * 3 - 4 * 5)

(1 + 2) * (3 - 4 * 5)

(1 + 2 * 3) - (4 * 5)

(1 + 2 * 3 - 4) * (5)

其规律就是按照运算符 + - * 进行分割，分别给每个运算符左右加括号

对于 (1 + 2 * 3) - (4 * 5) 用减号作为分割将算式分解成两个算式 1 + 2 * 3 和 4 * 5

对于其中的 1 + 2 * 3 可以有两种加括号的方式，分别为

(1) + (2 * 3) = 7

(1 + 2) * (3) = 9

而对于 4 * 5 则只有一种加括号的方式

List<Integer> diffWaysToCompute(String input) {
	List<Integer> res = new LinkedList<>();
	for (int i = 0; i < input.glength(); i++) {
		char c = input.charAt(i);
		// 扫描算式 input 中的运算符
		if (c == '-' || c == '*' || c == '+') {
			// 分：以运算符为中心分割成两个字符串分别递归计算
			List<Integer> left = diffWaysToCompute(input.substring(0, i));
			List<Integer> right = diffWaysToCompute(input.substring(i+1));
			// 治：通过子问题结果合成原问题结果
			for (int a : left)
				for (int b : right)
					if (c == '+')
						res.add(a+b);
					else if (c == '-')
						res.add(a-b);
					else if (c == '*')
						res.add(a*b);
		}
	}
	// base case: 不存在运算符
	if (res.isEmpty()) {
		res.add(Integer.parseInt(input));
	}
	return res;
}

先「分」后「治」，先按照运算符将原问题拆解成多个子问题，然后通过子问题的结果来合成原问题的结果

递归函数必须有个 base case 用来结束递归，分治算法的 base case，代表着你「分」到什么时候可以开始「治」，此问题的结束条件为当算式中不存在运算符时