给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1），每段绳子的长度记为k[0],k[1],...,k[m]。请问k[0]xk[1]x...xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
法1：递归
public class Solution { public int cutRope(int target) { if(target==1) return 1; if(target==2) return 1; if(target==3) return 2; return cut(target); } public int cut(int target){ if(target<4){ return target; } int ret = 0; for(int i = 1; i<target; i++){ ret = Math.max(ret, cut(i)*cut(target-i)); } return ret; } }
法2：动态规划：我觉得cyc大佬的动态规划写的不好，太简略了，没有直观体现动态规划和递归的区别，递归是从上到下，有很多重复计算的地方，动态规划是从下到上
public class Solution { public int cutRope(int target) { if(target == 0) return 0; if(target == 1) return 0; if(target == 2) return 1; if(target == 3) return 2; int[] ret = new int[target+1]; ret[0] = 0; ret[1] = 1; ret[2] = 2; ret[3] = 3; for(int i =4; i < target+1; i++){ for(int j = 1; j < i/2+1; j++){ ret[i] = Math.max(ret[i], ret[j]*ret[i-j]); } } return ret[target]; } }
法3：贪心
public class Solution { public int cutRope(int target) { if(target==1) return 1; if(target==2) return 1; if(target==3) return 2; int timeof3 = target/3; if(target - 3*timeof3 == 1) timeof3--; int timeof2 = (target - 3*timeof3)/2; return (int)Math.pow(3, timeof3) * (int)Math.pow(2, timeof2); } }
原文：https://www.cnblogs.com/tendermelon/p/12832941.html