14(1)-剪绳子

给你一根长度为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。

动态规划

使用f(n)表示长度为n的绳子的最大乘积，那么f(8)是如何得到的呢？

我们可以退一步想，f(8)一定是以下这些值的最大值，

f(7)*1 f(6)*2 f(5)*3 f(4)*4 f(3)*5 f(2)*6 f(1)*7

另外，对于f(3)，其乘积最大值的情况是分成1,2两段，但在作为求解f(8)时，需要注意长度为3的绳子本身可以作为3来使用，所以实际需要求以下数据的最大值。

max(f(7),7)*1 max(f(6),6)*2、max(f(5),5)*3、max(f(4),4)*4、max(f(3),3)*5、max(f(2),2)*6、max(f(1),1)*7

再另外，对于动态规划，很容易出现重复求值的情况，比如计算f(8)，需要计算f(7)，f(6)等，计算f(7)时，依然需要计算f(6)，所以为了提高计算速度，会使用一个map将中间的值记录。

Map<Integer, Long> dptable = new HashMap<>();  //缓存中间的计算过程
public int cutRope(int target) {
        if (target < 2) {
            return 1;
        }
        if (dptable.containsKey(target)) {//如果存在，直接用就行。
            return dptable.get(target);
        }
        int value = 0;
        for (int i = 1; i < target; i++) {
            value = Math.max(value, Math.max(cutRope(target - i), target - i) * i); //将问题分解成小问题计算。
        }
        dptable.put(target, value);
        return value;
    }

总结，这一类的问题，可以用一句中国的俗语来解释。

退一步，海阔天空

将大问题，先分解为小问题，小问题解决了，大问题也就得以解决。正所谓以退为进。

数学方法

数学方法就比较高端了，简而言之，将绳子分成长度为3的小段可以得到最大的乘积，具体的证明

public int cuttingRope(int n) {
        if(n == 2){
            return 1;
        }
        if(n == 3){
            return 2;
        }
  //上面先解决最基本的情况
        long res = 1;
        while(n > 4){ //只要绳子还大于4，就从里面切3长度的绳子
            res *= 3; 
            n -= 3;
        }
        return (int) (res * n );
    }

通过这种数学方法，最后的解法实际就是计算该绳子里最多可以切成多少个3长度的小段，这里注意当长度=4时是特殊情况。

我记得有一个编程大赛中的一道题目，有位选手就是直接推导出了数学公式，一行代码秒杀之。