思想分类
- 分治是把一个大规模的问题不断地变小然后进行推导的过程。
- 回溯则是从问题的起始点出发，不断地进行尝试，回头一步甚至多步再做选择，直到最终抵达终点的过程。
分治
思想
将一个问题的规模变小，然后再利用从小规模问题中得出的结果，结合当前的值或者情况，得出最终的结果。
模板
function fn(n) {
// 第一步：判断输入或者状态是否非法？
if (input/state is invalid) {
return;
}
// 第二步：判读递归是否应当结束?
if (match condition) {
return some value;
}
// 第三步：缩小问题规模
result1 = fn(n1)
result2 = fn(n2)
// 第四步: 整合结果
return combine(result1, result2)
}
复杂度
公式法可以说是计算递归函数复杂度最方便的工具，当递归函数的时间执行函数满足如下的关系式时，我们可以利用公式法：T(n) = a×T(n/b) + f(n)。其中，f(n) 是每次递归完毕之后额外的计算执行时间。例如，在归并排序中，每次递归处理完两边的数组后，我们需要执行合并的操作，那么这个操作的执行时间就是 f(n)。当参数 a、b 都确定的时候，光看递归的部分，它的时间复杂度就是：O(n^logba)。
由于时间复杂度求的是上界（upper bound)，通过对比递归部分的时间复杂度和 f(n) 的大小关系，得出最后的整体时间复杂度。牢记以下三种情况和相应公式：
当递归部分的执行时间 nlog(b)a 大于 f(n) 的时候，最终的时间复杂度就是 O(n^logba)。
当递归部分的执行时间 nlog(b)a 小于 f(n) 的时候，最终的时间复杂度就是 f(n)。
当递归部分的执行时间 nlog(b)a 等于 f(n) 的时候，最终的时间复杂度就是 O(n^logba)logn。
回溯
思想
在回溯算法里，是一步一步地小心翼翼地进行向前试探，会对每一步探测到的情况进行评估，如果当前的情况已经无法满足要求，那么就没有必要继续进行下去。
回溯算法的特点在于，当出现非法的情况时，算法可以回退到之前的情景，可以是返回一步，有时候甚至可以返回多步，然后再去尝试别的路径和办法。
模板
function fn(n) {
// 第一步：判断输入或者状态是否非法？
if (input/state is invalid) {
return;
}
// 第二步：判读递归是否应当结束?
if (match condition) {
return some value;
}
// 遍历所有可能出现的情况
for (all possible cases) {
// 第三步: 尝试下一步的可能性
solution.push(case)
// 递归
result = fn(m)
// 第四步：回溯到上一步
solution.pop(case)
}
常见解题思路
分治
回溯
注意事项
- 将回溯的结果列表保存为全局变量可以加速程序