题目:
给你一根长度为n的绳子,请把绳子剪成m段 (m和n都是整数,n>1并且m>1)每段绳子的长度记为k[0],k[1],…,k[m].请问k[0]k[1]…*k[m]可能的最大乘积是多少?
例如,当绳子的长度为8时,我们把它剪成长度分别为2,3,3的三段,此时得到的最大乘积是18.
public class 剪绳子 { public static int jsz2(int length) { if(length < 2) { return 0; } if(length == 2) { return 1; } if(length == 3) { return 2; } //length大于5,则尽可能多的剪长度为3的 int time3 = length/3; //如果剪3的剩余1,也就是存在剩4的情况,则拿出一个3 if(length - time3*3 == 1) { time3 -= 1; } //剪3的次数等于剩余长度/2 int time2 = (length - time3*3)/2; return (int)((Math.pow(3, time3))*(Math.pow(2, time2))); } public static int jsz1(int length) { if(length < 2) { return 0; } if(length == 2) { return 1; } if(length == 3) { return 2; } // 将最优解存储在数组中 int[] res = new int[length+1]; // 数组中第i个元素表示把长度为i的绳子剪成若干段之后的乘积的最大值 res[0] = 0; res[1] = 1; res[2] = 2; res[3] = 3; int max = 0; // 求出所有可能的f(j)*f(i-j)并比较出他们的最大值 for(int i = 4;i <= length;i++) { max = 0; for(int j = 1;j <= i/2;j++) { int re = res[j]*res[i-j]; if(max < re) { max = re; } res[i] = max; } } max = res[length]; return max; } public static void main(String[] args) { System.out.println(jsz1(8)); System.out.println(jsz2(8)); } }