用java计算绳长

java计算绳长"/>

用java计算绳长

题目还原：

给你一根长度为n的绳子，请把绳子剪成m段，记每段绳子长度为k[0],k[1]…k[m-1],求k[0]k[1]…k[m-1]的最大值。已知绳子长度n为整数，m>1(至少要剪一刀，不能不剪)，k[0],k[1]…k[m-1]均要求为整数。例如，绳子长度为8时，把它剪成3-3-2，得到最大乘积18；绳子长度为3时，把它剪成2-1，得到最大乘积2。

分析：要求的是乘积的最大值，因此可以定义一个函数f(n)表示长度为n的绳子剪成若干段后各段乘积的最大值。如果我们剪了1刀，那么可以有n-1种可能(1，2，3，…n-1)；剪了2刀，剩下的可以有n-2种可能；推广到i刀，可以有n-i种可能。即f(n) = max(f(i)*f(n-i))。这个类似于斐波那契数列，但是在斐波那契数列中我们都知道，按照原始定义的形式并不是一个好方法，用迭代法可以获得更好的性能，因此，这里也采用迭代法。即剑指offer中说的从下而上的顺序，先得到f(2),f(3)，再得到f(4),f(5)，…一直到f(n)。下面重点就是解决max(f(i)*f(n-i))，可以在循环中，用类似选择排序的思想，用一个临时变量记录当前最大值，然后后面的依次和最大值进行比较，循环结束后，最大值即当前长度的最大乘积。代码如下：

public class 剪绳子 {

public static int maxAfterCutting(int length) {

if (length < 2) {

return 0;

}

if (2 == length) {

return 1;

}

if (3 == length) {

return 2;

}

int[] products = new int[length + 1]; // 将最优解存储在数组中

// 数组中第i个元素表示把长度为i的绳子剪成若干段之后的乘积的最大值

products[0] = 0;

products[1] = 1;

products[2] = 2;

products[3] = 3;

int max = 0;

for (int i = 4; i <= length; i++) { //i表示长度

max = 0;

for (int j = 1; j <= i / 2; j++) { //由于长度i存在(1，i-1)和(i-1，1)的重复，所以只需要考虑前一种

int product = products[j] * products[i - j];

if (product > max) {

max = product;

}

}

products[i] = max;

}

return products[length];

}

}