解释

顾名思义，分治问题由“分”（divide）和“治”（conquer）两部分组成，通过把原问题分为子 问题，再将子问题进行处理合并，从而实现对原问题的求解。我们在排序章节展示的归并排序就 是典型的分治问题，其中“分”即为把大数组平均分成两个小数组，通过递归实现，最终我们会得到多个长度为 1 的子数组;“治”即为把已经排好序的两个小数组合成为一个排好序的大数组， 从长度为 1 的子数组开始，最终合成一个大数组。

可以使用主定理来求解时间复杂度

表达式问题

为运算表达式设计优先级

一般这种分治法都是使用递归来进行求解。题如下

func diffWaysToCompute(expression string) []int {
   var ways []int
   // 遍历整个字符串
   for i:=0;i< len(expression);i++ {
      c:=string(expression[i])
      // 首先我们判断当前的符号是否为运算符
      if c=="+" || c=="-" || c=="*" {
         // 如果是运算符的那么就分别计算左右两边的和
         // 这里实际上就已经把左右两边所有的情况都计算进去了
         left:=diffWaysToCompute(expression[:i])
         right:=diffWaysToCompute(expression[i+1:])
         // 下面我们就只需要依次组合计算
         for _,l:=range left{
            for _,r:=range right{
               // 判断运算符的类型并把结果放入我们的结果数组
               switch c {
               case "+":
                  ways = append(ways, l+r)
               case "-":
                  ways = append(ways, l-r)
               case "*":
                  ways = append(ways, l*r)
               }
            }
         }
      }
   }
   // 如果结果为空，说明只有数字，我们直接转换一下即可
   if len(ways)==0 {
      if n,err:=strconv.Atoi(expression);err==nil{
         ways=append(ways,n)
      }
   }
   return ways
}