面试题14：剪绳子 动态规划

[chejdj]

我看了一下，代码是没有问题，但我觉得思路有一点问题，书中的代码是这样的 private int maxProductAfterCounter1(int length){ int max=0; if(length<2)return 0; if(length==2)return 1; if(length==3)return 2; int[] product =new int[length+1]; product[0]=0; product[1]=1; product[2]=2; product[3]=3; for(int i=1;i<=length;i++){ max=product[i]; for(int j=1;j<=i/2;j++){ int temp=product[j]product[i-j]; if(temp>max)max=temp; } product[i]=max;
} max=product[length]; return max; } 这里面没有解释为什么从4开始，为什么长度为4的就必须要剪开，当然我们可以推算出4以后，它每次剪开的乘积都会大于本身，但是没有数学推算，自己写了一个，先假设每一个product最大值是自己本身，由于1，不能剪是自己，2剪了之后没有本身大 private static int maxProductAfterCounter(int length){ int max=0; if(length<2)return 0; if(length==2)return 1; if(length==3)return 2; int[] product =new int[length+1]; for(int i=1;i<=length;i++) product[i]=i; for(int i=1;i<=length;i++){ max=product[i]; for(int j=1;j<=i/2;j++){ int temp=product[j]product[i-j]; if(temp>max)max=temp; } product[i]=max;
} max=product[length]; return max; }