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

感谢大佬，参考的是他的笔记才懂了这题，他写的真的很好，感谢感谢！

题目

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

分析题目

像这种题目只要列一下式子很自然就会想到要用动态规划来解决。
注意点：绳子长度都是整数而且剪出来的每一段绳子长度依然是整数（就是每次也是剪整数长度的绳子出来）。n>1且m>1,绳子长度肯定大于1且每次至少将绳子剪成两段，不能不剪。

解题方法

首先是一些特殊的值，当绳子长度<=3的时候，这些是需要首先输出的，跟后面的product[0][1][2][3]值不一定一样，这里返回的这些是绳子长度小，必须要剪一段的话（题目要求必剪），得到的一些返回值。

定义：绳子长度为i时，最大乘积为dp[i]。
子问题：如果设j为剪一刀之后绳子的长度，有dp[i]=dp[j]*dp[i-j]，即i长度的绳子剪一刀之后最大乘积等于两段绳子继续剪开的最大乘积。

结合代码

public class Solution {
    public static int cuttingRope(int length) {
    	//如果绳子长度<=1,必须剪一刀也没法剪出来，返回0
        if(length < 2) {
            return 0;
        }
        //如果绳子长度=2，只能剪一刀，1*1，返回1
        if(length==2){
            return 1;
        }
        //如果绳子长度=3，剪一段下来乘积1*2最大，返回2
        if(length==3){
            return 2;
        }
        int max_product;
        //设置一个数组放dp[]结果
        int []products =new int[length+1];
        //for循环里面是已经剪过的绳子才会用到前面的products,所以这里放的是不一定需要剪的绳子；比如products[3]如果不剪=3，如果剪成两段就是1*2，剪成三段就是1*1*1，所以不剪是max,products[3]=3
        products[0]=0;
        products[1]=1;
        products[2]=2;
        products[3]=3;
        //为什么从4开始？看注释1处
        for(int i=4;i<length+1;i++)
        {
        	//每次开始计算一个dp[i]的时候，都设置为一个存放当前最大dp[i]的空间，在这里直接复用max_product,最开始设置为0
            max_product = 0;
            //注释2处
            for (int j=1;j<(i/2 + 1);j++){
            	//每次跟现有的最大值对比一下，如果后者大，就更改最大值
                max_product = Math.max(max_product, products[j] * products[i - j]);
            }
            //dp[i]=每次求出来的max_product
            products[i]=max_product;
        }
        return products[length];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

注释1处：为什么从4开始？这个问题也相当于为什么products设置初始值的时候只设置到3为止。由于题目要求的必须要剪一刀，因此会导致当所给的绳子长度是小于4的时候，剪完之后的长度小于剪之前的长度，但这最开始我们已经处理过了那些特殊情况。放在products里面的是不是必剪的。问题转换为dp[ ]dp[]什么时候>=i?即剪断绳子什么时候会比不剪断的最大乘积要大或者相等？假设只剪一刀，对半剪断，最大乘积就是(i/2)(i/2)，(i^2)/4>=i解的i>=4，所以当i>=4的时候肯定剪断绳子比不剪断绳子的最大乘积要大。

注释2处：j事实上可以取1到（i-1），但是这里其实进行了优化，比如求dp[5]=dp[1]*dp[4]=dp[2]*dp[3]=dp[3]*dp[2]=dp[4]*dp[1]，对称的计算删掉。

写的不对的请大佬们多多指教