剑指offer第二版面试题14：剪绳子 Java

题目描述：
考虑一条长度为n的绳子，请将其分割成m个部分（其中均为正整数且均大于1）。设各部分长度分别为k_0,k_1,…,k_{m-1}（注意索引从0到m-1），求这些部分乘积的最大值是多少？
比如当绳长是8时，请将其分为\{2,3,3\}三个部分，则其乘积最大值为2\times 3\times 3= 18。

分析：

1. 寻求解决某类问题的整体最优解；
2. 整体优化目标依赖于各子优化目标实现；
3. 将复杂的大任务划分为若干个子任务；
4. 这些子任务是相互关联且共享更小规模子任务的；
5. 通过存储各子任务的最佳解决方案来避免重复计算；
6. 基于以上分析可知该问题是采用动态规划方法进行求解。

动态规划：

1. 定义函数f(n)用来衡量将长度为n的绳子分割成多段后各部分长度乘积的最大值。
2. 在第一次切割时有n-1种不同的选择可用。
3. 显然这是一个自顶向下的递归过程，在这种情况下存在大量重复计算的问题。因此我们采用自底向上的动态规划策略，并将所有子问题的最优解存储下来以避免重复计算。
4. 需要注意的是，在计算过程中这两种情况被视为等同：即n \times i与(n-i)\times i被认为是相同的两种情况。
5. 特别地，在本题