求解递归式$T(n) = \max_{i=1}^{n-1} T(i) + T(n-i) + i (n-i)$

你的思路完全找对了方向！带$\max$的递归式处理的核心，就是先搞清楚哪个$i$能让右边的表达式取到最大值——甚至有时候会出现所有$i$对应的结果都一样的情况，就像这个例子。接下来一步步拆解：

第一步：分析$\max$对应的$i$值 #

先看表达式里的$i(n-i)$，这是个开口向下的二次函数，顶点在$i=n/2$，所以这个项在$i=n/2$时最大。但我们还要结合$T(i)+T(n-i)$来看整体值。

先代入小的$n$值验证：

• $n=2$：只能取$i=1$，$T(2)=2T(1)+1$
• $n=3$：$i=1$时结果是$T(1)+T(2)+2=3T(1)+3$；$i=2$时结果完全相同
• $n=4$：$i=1$时是$T(1)+T(3)+3=4T(1)+6$；$i=2$时是$2T(2)+4=4T(1)+6$，结果还是一样

这看起来不管$i$取什么，右边的结果都相等？我们可以假设$T(n)$是二次函数，比如$T(n)=an^2+bn+c$，代入递归式验证：
把$T(i)+T(n-i)+i(n-i)$展开后，会发现当$a=1/2$、$c=0$时，$i$的一次项和二次项系数都会抵消，最终结果等于$\frac{1}{2}n^2 + bn$，刚好和$T(n)$的形式一致。结合初始条件$T(1)=k$（$k$是常数），可以得到$T(n)=kn + \frac{n(n-1)}{2}$。

第二步：用数学归纳法严格证明 #

我们用归纳法证明$T(n)=kn + \frac{n(n-1)}{2}$（其中$k=T(1)$）：

1. 基例：$n=1$时，$T(1)=k1 + \frac{10}{2}=k$，符合初始条件；$n=2$时，$T(2)=2k+1$，和直接计算的结果一致。
2. 归纳假设：假设对于所有$m < n$，$T(m)=km + \frac{m(m-1)}{2}$成立。
3. 归纳步骤：对于任意$1 \leq i \leq n-1$，计算右边的表达式：
   $$
   \begin{align*}
   T(i)+T(n-i)+i(n-i) &= \left(ki + \frac{i(i-1)}{2}\right) + \left(k(n-i) + \frac{(n-i)(n-i-1)}{2}\right) + i(n-i) \
   &= kn + \frac{i^2 -i + (n-i)(n-i-1)}{2} + ni -i^2 \
   \end{align*}
   $$
   展开并化简分子部分：
   $$
   i^2 -i + (n-i)(n-i-1) = 2i^2 -2ni +n^2 -n
   $$
   代入后继续化简：
   $$
   kn + \frac{2i^2 -2ni +n^2 -n}{2} + ni -i^2 = kn + \frac{n^2 -n}{2}
   $$
   这正好等于$T(n)=kn + \frac{n(n-1)}{2}$。

因为对于所有$i$，右边的结果都等于$T(n)$，所以$\max$操作其实不影响结果——不管选哪个$i$，得到的都是同一个值。

结论 #

• 你猜测的$T(n)=\mathcal{O}(n^{2)$完全正确，而且实际上$T(n)=\Theta(n}2)$，因为它是严格的二次函数。
• 你怀疑$i=n/2$时取最大值，这里其实所有$i$对应的结果都相同，所以$\max$可以取任意$i$，当然包括$i=n/2$。

内容的提问来源于stack exchange，提问作者Banach Tarski