最近看《剑指Offer第二版》有这么一道面试题：
题目：给你一根长度为n的绳子，请把绳子剪成m段 (m和n都是整数，n>1并且m>1)每段绳子的长度记为k[0],k[1],…,k[m].请问k[0]k[1]…k[m]可能的最大乘积是多少？例如，当绳子的长度为8时，我们把它剪成长度分别为2,3,3的三段，此时得到的最大乘积是18。
书上讲了一种贪婪算法：
当n≥5时，我们尽可能多地减长度为3的绳子；当剩下的绳子长度为4时，把绳子剪成两段长度为2的绳子（其实这时候没必要再减了，只不过题目要求至少剪一刀）。
首先，当n≥5时，我们可以证明2(n-2)>n并且3(n-3)>n。也就是说，当绳子剩下的长度大于或者等于5的时候，我们就能把它剪成长度为3或者2的绳子段。另外，当n≥5时，3(n-3)≥2(n-2)，因此我们应该尽可能多地剪长度为3的绳子段。
下面是我的思路，首先是基本不等式的推广：
一般地，若a1,a2,a3,...an是正实数，则有
所以可以把这道题转换成下面这个问题：
已知函数：
当m取几的时候，f(m)最大？条件是m和n/m都是正整数。
求导一下，得：
于是可得，当m≤n/e时，函数单调递增；当m≥n/e时，函数单调递减，所以当m=n/e时（此时n/m=e），f(m)取到最大值（e是自然常数）。下面是f(m)的图像：
但是n/e和e显然不是正整数（条件是m和n/m都是正整数），这时候取离n/e最近的两个整数横坐标就行，但是这时候n/m（也就是每段绳子的长度）不一定是整数！而且之前的大前提是每段绳子长度都相等时才取到最大值（也就是基本不等式中的a1，a2，...都相等时取等号）。这我就很尴尬了。
没办法，只能换个思路。根据题意可以得出公式：f(n)=max(i×f(n-i))，其中1≤i≤n, n≥1, 且n,i都是整数。这里的i就相当于第一刀剪了长度为i的一段，然后这段就确定了，之后再也不会剪了。
我们设g(i)=i×f(n-i)
当i≥5时:
i×f(n-i)≤(i-2)×2×f(n-i) //因为当i≥5时，有i≤(i-2)×2
i×f(n-i)≤(i-2)×f(n-i+2) //因为2×f(n-i)=2×f(n-i+2-2)≤f(n-i+2)，（因为f(n)=max(i×f(n-i)),这里n取n-i+2，i取2就行了）
i×f(n-i)≤(i-2)×f(n-(i-2))
即g(i)≤g(i-2)
这个结论告诉我们：
g(3)≥g(5)≥g(7)≥g(9)≥...
g(4)≥g(6)≥g(8)≥g(10)≥...
而如果我们能证明g(1)、g(2)、g(4)都小于g(3)的话，那么g(3)就是所有g(i)中最大的。（至于为什么是3，因为一会儿会在g(2)和g(3)中决胜负）
首先如果g(1)是最大的，那就说明f(n)=1×f(n-1)，这样的话对于任意的n, f(n)都相等，显然矛盾。
其次，g(4) = 2×2×f(n-4) ≤ 2f(n-2) = g(2)
所以，最终就是要比较g(2)和g(3)谁大，没办法只能祭出大招了，数学归纳法。
当n=5时，有3f(2) ≥ 2f(3)，所以g(3) ≥ g(2)成立
当n=6时，有3f(3) ≥ 2f(4)，所以g(3) ≥ g(2)成立
假设当n=k时，3f(k-3) ≥ 2f(k-2)成立，从而得到f(k)=3f(k-3)
n=k+1时，3f(k+1-3) ≥ 2f(k+1-2)成立，即3f(k-2) ≥ 2f(k-1)，从而得到f(k+1)=3f(k+1-3)
当n=k+3时，
需要证明3f(k+3-3) ≥ 2(k+3-2)
就是要证明3f(k) ≥ 2(k+1)
就是要证明3(3f(k-3)) ≥ 2(3f(k+1-3))
就是要证明3f(k-3) ≥ 2f(k-2)
证明完毕
（ 其实还要再手动算个n=7的情况，这样就可以这样推导了：(5,6)=>8 ; (6,7)=>9 ; (7,8)=>10 ; (8,9)=>11 ;...）
所以现在就可以得到g(3)≥g(i)的结论了，所以f(n)=3f(n-3)，因为i≥5,所以n肯定也要≥5。