问题描述

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

输入描述

输入一个数n，意义见题面。（2 <= n <= 60）

输出描述

输出答案。
例如： 输入8 ，输出18。

解题思路

1. 拿到问题首先是简单试了几个值，没有发现啥规律（其实有，有兴趣可以去搜一下）
2. 对于问题的几个约束简单明确一下：
   1）首先：切出1长度是没有意义的
   2）由1我们可以得知，对于任意长度的绳子，我们只需考虑n-2—2长度的情况。
   3）极端值：比如2和3的值就是不切，即m=1，因为他们不论怎么切，都会切出1来。
3. 一开始觉得是一个递归过程，尝试了几次，感觉总是设计不好递归结构。
4. 在尝试的过程中，发现整个问题存在大量的重复计算，即可以看做一个典型的重叠子问题过程，借用牛客上答案区画的图解：不难发现，出现了大量的重复过程。所有可以利用动态规划来做。
5. 即我们需要开辟一个数组，从小（简单）到大（复杂）来记录每个位置的最优解，当我们在计算更大值的时，我们就可以从之前的计算结果直接拿来使用。

DP 公式

$f(n)=\begin{cases} max(2*f(n-2),3*f(n-3)...(n-2)*f(2)) & n >3\\ 3 & n=3\\ 2 & n=2\\ \end{cases}$

Code

    public int cutRope(int target) {int[] arr = new int[target+1];// 先对边界值进行初始化arr[2] = 2;arr[3] = 3;if (target < 4) return arr[target];for (int i = 4; i <= target; i++) {
//            从4开始填表，一直填到targetint max = 0;//建立dp表，对应公式里面的max（....）for (int j = 2; j < i; j++) {int count = j * arr[i - j];max = count > max ? count : max;}arr[i] = max;}return arr[target];}