分治法将复杂问题分解为若干子问题（子问题再分解为子子问题，直到问题被分解得足够小，能够直接得出解），再将子问题的解合并，得到最终解。不同于动态规划，分治法中的父问题仅依赖其下一层的子问题，而不会有跨层级的直接依赖。
🤔 分治思想有什么好处呢？（摘自 leetcode）
-
简化思维逻辑
原始问题往往非常复杂，例如排序问题。假设原始我们需要考虑对 1000 个数进行排序，那么利用分治思想我们可以分别对左右的 500 个数进行排序，然后考虑合并两个有序数组。当然，排序 500 个数看起来仍然不容易，但是我们可以继续分治下去，最终我们只需要考虑 1~2 个数的排序策略，这就是经典的归并排序的思想。
-
分布式算法
虽然在算法学习的过程中少有接触多进程和分布式等思想。但是随着 CPU core 越来越多，能够被分治法拆解的问题显然更方便进行并行计算，从而节省总体时间。因此分治思想在工程实现上具有重要的意义。
-
效率优化（并行计算情况下）
虽然我们不常用并行解决算法问题，但是在某些情况下仍然能够帮助我们节省计算代价，代表就是快速幂算法。
根据《算法导论》中的阐述，分治策略在递归地求解的过程中，其每一层递归应用了如下三个步骤：
-
分解（Divide）
将问题划分为若干子问题，子问题的形式与愿问题一样，只是规模更小。
-
解决（Conquer）
如果子问题的规模足够小，则停止递归，直接求解。
-
合并（Combine）
将子问题的解组合成原问题的解。
我们同样从典型的基础题入手，之后再讲一些拐弯的题。
最大连续数列 #
对于任何一个数组，我们关心三个值：从数组最左端起连续数列的最大和 leftLarge、从数组右侧起连续数列的最大和 rightLarge、整个数组中（不要求从左端起或从右端起）连续数列的最大和 wholeLarge。我们将其构成三元组（leftLarge， rightLarge，wholeLarge）。对于只有一个元素的数组，leftLarge、rightLarge、wholeLarge 的值自然都等于该元素。而对于长度大于 1 的数组，我们从中间将其划分成两段，分别计算各段的三元组。本数组的三元组则是由左右两段数组的三元组计算得来。
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
def cal(nums, start, end):
if start >= end:
return (nums[end], nums[end], nums[end])
mid = (start + end) // 2
leftRet = cal(nums, start, mid)
rightRet = cal(nums, mid + 1, end)
leftLarge = max(leftRet[0], sum(nums[start: mid + 1]) + rightRet[0])
rightLarge = max(rightRet[1], sum(nums[mid + 1: end + 1]) + leftRet[1])
wholeLarge = max(leftRet[2], rightRet[2], leftLarge, rightLarge, leftRet[1] + rightRet[0])
return(leftLarge, rightLarge, wholeLarge)
ret = cal(nums, 0, len(nums) - 1)
return ret[2]💡 另外，此题也可以通过动态规划解决（且更优雅），不在此处展开，具体可查看题解。
搜索二维矩阵 #
此题与上一题的差别其实并不大，不过是从一维数组转变成了二维数组。自然地，分治规模也从原来的分为两段，变成了分成四块。
由于其左右递增、上下递增的排列特性，对于其中任意一个矩阵来说，其左上角的元素为最小值，右下角的元素为最大值。如果 target 不在这个区间内，我们则可以迅速的判断该矩阵中没有我们要找的元素。
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
def divide(i, j, k, l):
if any(w < 0 for w in [i, j, k, l]) or any(w >= len(matrix) for w in [i, k]) or any(w >= len(matrix[0]) for w in [j, l]):
return False
if i > k or j > l:
return False
if target < matrix[i][j] or target > matrix[k][l]:
return False
if i == k and j == l:
return target == matrix[i][j]
midRow = (i + k) // 2
midCol = (j + l) // 2
return divide(i, j, midRow, midCol) or divide(i, midCol + 1, midRow, l) or divide(midRow + 1, j, k, midCol) or divide(midRow + 1, midCol + 1, k, l)
return divide(0, 0, len(matrix) - 1, len(matrix[0]) - 1)至少有 K 个重复字符的最长子串 #
此题的有意思之处在于逆向思维，瞄准那些无法满足条件的字符，将其作为分治的分割点。
题目要求子串中的每一个字符出现的次数都不少与 k，我们在分治之前先计算当前串中各个字符出现的次数，对于那些出现次数少于 k 的字符来说，无论其怎么分，更不可能在子串中满足 k 次的出现。因此任何子串想要满足条件，都不能包含该字符。我们索性以该字符作为分治的分割条件，递归地计算分割后的各个子串。
而当某个子串中我们找不出出现此处小于 k 的字符，则说明整个字串都满足条件，我们返回子串的长度。
class Solution(object):
def longestSubstring(self, s, k):
if not s:
return 0
for c in set(s):
if s.count(c) < k:
return max(self.longestSubstring(t, k) for t in s.split(c))
return len(s)为运算表达式设计优先级 #
给定一个含有数字和运算符的字符串，为表达式添加括号，改变其运算优先级以求出不同的结果。你需要给出所有可能的组合的结果。有效的运算符号包含 +, - 以及 * 。
示例 1:
输入: "2-1-1"
输出: [0, 2]
解释:
((2-1)-1) = 0
(2-(1-1)) = 2
示例 2:
输入: "2*3-4*5"
输出: [-34, -14, -10, -10, 10]
解释:
(2*(3-(4*5))) = -34
((2*3)-(4*5)) = -14
((2*(3-4))*5) = -10
(2*((3-4)*5)) = -10
(((2*3)-4)*5) = 10如果没有接触过分治思想，这一题乍一看可能会有点难，但是学习过分治后，就会很容易想到，括号这种东西，不就是为了划分领地嘛。加上括号了，就能保证我括号内计算的完整性。
因此我们可以以运算表达式为分割点对字符串进行分治处理。具体来说，当我们瞄准一个运算符的时候，比如说是 * 号，那么就可以在这个 * 的左右画上括号，变为 () * ()，得到的结果就是左边括号里的值，乘以右边括号里的值。而左边括号又有多种可能的划分，右边括号又有多种可能的划分，因此左右两边的结果应该是两个数组，最终结果等于两个数组中元素的交叉相乘。