题解 | #剪绳子#
剪绳子
http://www.nowcoder.com/practice/57d85990ba5b440ab888fc72b0751bf8
思路: 前三个数定义在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];
}
}