剑指offer67-剪绳子

刷了这么多天题目，终于刷到剑指offer的最后一道题目了，刷完继续努力在刷200道leetcode的medim题目。

给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1），每段绳子的长度记为k[0],k[1],...,k[m]。请问k[0]xk[1]x...xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

依据经验，这种求最大最小值的题目，不是用动态规划就是用贪心算法来解决，因为是最值，所以以为这要遍历尽可能多的解决方案并对这写方案作出判断。
这道题目对绳子的要求是一定要切割。
动态规划求解问题的四个特征：
①求一个问题的最优解；
②整体的问题的最优解是依赖于各个子问题的最优解；
③小问题之间还有相互重叠的更小的子问题；
④从上往下分析问题，从下往上求解问题

因此可以从小的绳子的最值开始进行推演。

public class Solution {
    pu