如何将剪绳子问题转化为长尾词优化策略？

本文共计890个文字，预计阅读时间需要4分钟。

一、题目：给你一根长度为n的绳子，请把它剪成长度为m的整段（m+n都是整数，n+1且m+1，m=n+n）每段绳子的长度记为k[1]，...，k[m]。

二、请问k[1]+k[2]+...+k[m]可能的最大的乘积是多少？

一、题目

给你一根长度为 n 的绳子，请把绳子剪成整数长的 m 段（ m 、 n 都是整数， n > 1 并且 m > 1 ， m <= n ），每段绳子的长度记为 k[1],...,k[m] 。请问 k[1]*k[2]*...*k[m] 可能的最大乘积是多少？例如，当绳子的长度是 8 时，我们把它剪成长度分别为 2、3、3 的三段，此时得到的最大乘积是 18 。

二、题解

2.1知识点：动态规划

动态规划得基本思想：将待求解的问题分解成若干个相互联系的子问题，先求子问题，然后从这些子问题的解得到原问题的解；对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，让以后再次遇到时直接引用答案，不必重新求解。动态规划算法将问题的解决方案视为一系列决策的结果。

2.2 解题思路

一旦分出一段长度为1的小段，只会减少总长度，乘积也不会增加，因此长度为2的绳子不分比分开乘积大

长度为3的绳子不分比分开大，长度为4的绳子分成2*2比较大。

同样递推，长度为n的绳子，可以尝试其中一段不可分的为j，如果另一段n-j最大乘积已知，可以遍历所有j找到这个最大乘积。

因此用dp[i]表示长度为i的绳子可以被剪出来的最大乘积，那么后续遍历每个j的时候，外卖取最大的dp[i]表示长度为i的绳子可以被剪出来的最大乘积，那么后续遍历每个j的时候，我们取最大的dp[i]=max(dp[i],j*dp[i-j])就好了。

//可以被分成两份 for(int j = 1; j < i; j++) //取最大值 dp[i] = max(dp[i], j * dp[i - j]);

2.3具体步骤

• step 1：检查当number不超过3的时候直接计算。
• step 2：用dp数组表示长度为i的绳子可以被剪出来的最大乘积，初始化前面4个容易推断的。
• step 3：遍历每个长度，对于每个长度的最大乘积，可以遍历从1到i的每个固定一段，按照上述公式求的最大值。
• step 4：最后数组最后一位就是答案。

import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param n int整型 * @return int整型 */ public int cutRope (int n) { // write code here if(n < 2) return 0; if(n < 4) return n -1; int[] dp = new int[n + 1]; dp[1] = 1; dp[2] = 2; dp[3] = 3; dp[4] = 4; for(int i = 5; i <= n;i++){ for(int j = 1;j <= i/2;j++){ dp[i] = Math.max(dp[i],dp[j] * dp[i-j]); } } return dp[n]; } }

2.4贪心算法

具体做法：

• step 1：按照上述思路，不超过3的直接计算
• step 2：超过3的不断累乘3，然后number不断减去3，直到最后不超过4。
• step 3：最后乘上剩余的数字。

Java实现代码：

public class Solution { public int cutRope(int target) { //不超过3直接计算 if(target <= 3) return target - 1; int res = 1; while(target > 4){ //连续乘3 res *= 3; target -= 3; } return res * target; } }