剑指offer 面试题14

剑指offer 面试题14

题目：给你一根长度为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.

思路：定义函数f(n)为长度为n的绳子剪成若干段后各段长度乘积的最大值。在剪第一刀的时候，我们有n-1种可能的选择，也就是剪出来的第一段绳子的长度分别为1,2...n-1。因此f(n)=max(f(i)*f(n-i))，其中0

代码：

public class Solution { public int maxNumAfterCutting(int n) { if (n < 2) return 0; // 绳子长度为2时，只能剪成1和1 if (n == 2) return 1; // 只可能为长度为1和2的2段或者长度都为1的三段，最大值为2 if (n == 3) return 2; // 当长度大于3时，长度为3的段的最大值时3 int product[] = new int[n+1]; product[0] = 0; product[1] = 1; product[2] = 2; product[3] = 3; int max = 0; for (int i = 4; i <= n; i++) { max = 0; for (int j = 1; j <= i / 2; j++) { int sum = product[j] * product[i - j]; if (sum > max) { max = sum; product[i] = max; } } } return product[n]; }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。