题解 | #剪绳子#

思路： 前三个数定义在dp方程当中，之后元素存储的是之前每一段的剪的最大值，因为之前的最大值已将放到数组当中，只需要进行调用就可以，因为题目并没有要求剪几段，可以是多段，只要有最大值就可以。

import java.util.*;
public class Solution {
    public int cutRope(int length) {
//参考https://wangwenqiang.blog.csdn.net/article/details/83184146?spm=1001.2101.3001.6650.1&depth_1-utm_relevant_index=2
//  if (length < 2) {
//             return 0;
//         }
//         if (length==2){return 1;}
//         if(length==3){return  2;}

//         //定义一个存放>=4 长度的数组 ，对>=4长度的最大的乘积进行临时存储
//         int[] products=new int[length+1];
//         products[1]=1;
//         products[2]=2;
//         products[3]=3;
//         for (int i = 4; i <=length; i++) {
//             int max=0;
//             for (int j = 1; j <=i/2; j++) {
//                 int product=products[j]*products[i-j];
//                 if (product>max){
//                     products[i]=product; }
//             }
        //差了一步
//         }
//         return    products[length];
        
         //长度小于2 无法分割
        if(length<2)
            return 0;
        //长度等于2 一分为二 1*1
        if(length==2)
            return 1;
        //长度等于3 最大为1*2=2
        if(length==3)
            return 2;
        //定义一个存放>=4 长度的数组 ，对>=4长度的最大的乘积进行临时存储
        int[] products=new int[length+1];
        //以下的前三个数组存放的不是最大值，而是长度值
        products[1]=1;
        products[2]=2;
        products[3]=3;
        for(int i=4;i<=length;i++) {
            int maxModify=0;
            for(int j=1;j<=i/2;j++) {
                int product=products[j]*products[i-j];
                if(product>maxModify)
                    maxModify=product;
            }    
            //得到f(i)的最优解
            products[i]=maxModify;
        }    
        //返回发f(n)
        return products[length];
     
    }
}