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

  首先正确理解题意，一段绳子，可以剪成多段，求最大乘积。里面有两个变量，一个是绳长，一个是减的段数。而给定绳长后，在编程过程中，主要考虑减的段数的变化。

思路1：动态规划。

  整体可由局部和局部的最优解相乘得到，如果把长度n绳子的最大乘积记为f(n)，则有：f(n)=max(f(i)*f(n-1))，因此不断由小推导至大，最终求出n的结果。因此设置一个数组用来存放对应的最大乘积数。
  然后本题很关键的一点是，推断的起点设计在4。最大乘积其实是反复出现2和3。规律如下：

  • 当target等于1，2，3的时候，结果是固定的
  • 当target大于3的时候，可以看以下数据
  • target=4, 最优解：2 2
  • target=5, 最优解：3 2
  • target=6, 最优解：3 3
  • target=7, 最优解：3 2 2
  • target=8, 最优解：3 3 2
  • target=9, 最优解：3 3 3
  • target=10,最优解：3 3 2 2
  • target=11,最优解：3 3 3 2
  • target=12,最优解：3 3 3 3

  因此，在使用递推公式时，必须由4开始使用。4前面的都当做特例分析了。刚刚提到设计了一个数组用来存放最大乘积值，这个表述并不是十分准确，准确表述是，product[i]表示，当剪操作后，绳子的某段长度变成i时，i可以减或者不减而形成的最大乘积值是多少。因此product[3]就是不操作而单独拿一个3。而不是3剪操作后形成的最大，如果3剪操作，最大也就1*2=2。所以这里的几个初始值很关键。

注意：很多人都设计了product[0]和product[1]，其实没必要，因为我们知道就是由2和3构成的，因此我们后续也只会用到2和3。所以下面的代码将很多题解中的代码进行一点优化。去掉了0和1的赋值，以及j从2开始而不是从1或者从0。

public class Solution {
    public int cutRope(int target) {
        if (target <= 1)//绳长1或者0执行剪操作
            return 0;
        if (target == 2)//绳长2执行剪操作
            return 1;
        if (target == 3)//绳长3执行剪操作
            return 2;
        int[] product = new int[target + 1]; // 用于存放最大乘积值
        //下面几个值设定的很重要。

        product[2] = 2;//剩余绳长为2可形成的最大乘积（可剪可不剪，不减就是直接拿2最大）
        product[3] = 3;//剩余绳长为3可形成的最大乘积（可剪可不剪，不减就是直接拿3最大）

        // 开始从下到上计算长度为i绳子的最大乘积值product[i]
        for (int i = 4; i <= target; i++) {
            int max = 0;
            for (int j = 2; j <= i / 2; j++) {//j到i/2即可，从i/2到i并不会更新最大值
            //且由于我们知道要么取2要么取3，因此我们也直接从j=2开始计算起。
                if (max < product[j] * product[i - j])
                    max = product[j] * product[i - j];
            }
            product[i] = max;
        }
        return product[target];
    }
}

思路2：贪心

  当我们发现了就是2和3构成最终解时，可以利用这两个数做文章。即将一个数分解成2和3.由解法1的规律可看到，我们是尽量能分成3就分成3，不能分成3的时候就用一个2.因此9是3个3而不是4个2.并且注意到，7不是分解成2个3和1个1，这是因为我们只分成2和3，如果剩下4这种模上3余1时，我们就用2个2代替（其实我们2的个数最多为2个最少没有）。根据此规律编写代码。贪心策略就是每次取当前的最佳状况，而本题的最佳状况就是能取3就取3，不能取的时候就用2代替.
  因此我们将给的长度n除以3，余数取决于2的个数，余0全是3，余1则是2个2（3的个数则是商减1），余2则说明就1个2.

public class Solution {
    public int cutRope(int target) {
        if (target <= 1)
            return 0;
        if (target == 2)
            return 1;
        if (target == 3)
            return 2;

        int x = target % 3;//看除以3余多少，来决定2的个数
        int y = target / 3;//看3的个数
        if (x == 0) {//全3
            return (int)Math.pow(3, y);//需要强制转换一下
        } else if (x == 1) {//2个2，剩余都是3，注意y要减1，比如4
            return 2 * 2 * (int)Math.pow(3, y - 1);
        } else {//x==2，只有1个2
            return 2 * (int)Math.pow(3, y);
        }
    }
}