孤独的黑鱼 题目描述: 将绳长大于1的绳子剪成m(m>=2)段,求n段绳长的总乘积和最大为 算法思想: 由于剪成长度为1的子绳会使乘积变小,故任何情况下(除n=2||n==3)的情况下,不应剪出长为1的子绳 当绳长为n时,如果存在某一点进行剪绳使得左右两边子绳的乘积和大于原来的绳长,则2*(n-2)>=n 得出n>=4 即当绳长大等于于4时可对其进行再剪切使乘积变大。因此对于绳长为n的绳子,剪成长度为2和3的子绳的情况下乘积最大 由一二行可以得出,绳长为4时,剪成2+2乘积最大,绳长>4时 令 i = n % 3 有以下三种情况 情况一: i=0 即n为3的整数倍(6、9、12·····),若n为偶数,则n剪成n/2个长度为2的子绳,3*3大于2*2*2, 因此,将n按每段为3切分的乘积大于按每段为2进行切分的乘积,当n为奇数时,对于n-3,其按3切分乘积最大, 考虑最后一个长为3的子绳,由上面可知 此时切分会使乘积变小,故不可切分,因此当n为3的整数倍时,按3切分结果最大 情况二: i = 1,去掉最后一个长为3的子绳,此时切分情况变为n-1-3和4,n-1-3为3的倍数,由情况一可知, 按3均分乘积最大,对于最后长为4的子绳,由上面的结论可知切分为2+2时乘积最大故此,i = 1时,应先按3切分,剩余长度为4时再按2切分 情况三: i= 2,此时,n - 2 为3的倍数,结合情况一二可知,此时先按3切分直到剩余长度为2时则不再切分结果最大 综合情况一二三可知,当剩余绳子长度大于4时,则按长为3不断切分,若剩余长度为4,则切分为2+2,若剩余长度小于4则不再切分。 public static int cutRope(int target) { if(target <= 3) return target - 1; if(target % 3 == 0 ) return (int) Math.pow(3, target / 3); if(target % 3 == 1 ) return (int) Math.pow(3, (target / 3) - 1 ) * 4; return (int) Math.pow(3, target / 3) * 2; } 希望大家多提意见建议,谢谢