关于leetcode 343问题的一点疑惑

Question

res = max3(res, i * (n - i) , i * breakInteger(n - i));
为什么这样就可以了？
比如9分成4+5的这种情况
为什么只用考虑
4 * 5， 4 * breakInteger(5)就可以了
不用考虑
4 * 5， 4 * breakInteger(5)， breakInteger(4) * breakInteger(5)??

还有就是比如n=5
为什么要考虑 （1,4）（2,3） （3,2） (4,1)
由于对称的，只考虑（1,4）（2,3）可以吗？

谢谢！

Answer 1

liuyubobobo 2018-09-28 16:18:38

因为，这个完整的过程，是在一个循环里面的：

for(int i = 1 ; i <= n - 1 ; i ++)    
    res = max3(res, i * (n - i) , i * breakInteger(n - i));

这个循环的过程，永远尝试先分解成一个相对较小的数字。所以，我们不需要考虑breakInteger(4) * breakInteger(5)。因为将breakInteger(4)分解，其中的一部分肯定比4小，比如是1，2，3，那么，这些情况，在i=1的时候，我们考虑1 + breakInteger(8)；i=2的时候，我们考虑2 + breakInteger(7)；i=3的时候，我们考虑3 + breakInteger(6)的时候，已经考虑过了。

换句话说，你也可以理解，这个循环考虑了将n分解成第一个数字是x，剩下的数字n-x继续分解的所有情况。因为x被遍历穷尽了了，n分解以后，第一个数字只有可能在1到n-1之间，所以，这个循环已经处理了所有可能：）

• 提问者 慕粉3520842 #1

  非常感谢！

• 慕移动5238665 #2

  1111