给你一根长度为n的绳子，请把绳子剪成m段（m,n都是整数，n>1并且m>1），每段绳子的长度乘积之和最大是多少？例如，当绳子长度为8，剪成长度分别为2,3,3的三段，此时得到最大乘积是18.
动态规划 首先要知道这是一个递归问题，极大的长度下的解肯定是一个不那么大的长度进一步得到的。dp数组作为存储最大值的数组，由小学数学知识我们知道，dp[1]=1,dp[2]=2,dp[3]=3. 继续往下思考的话，dp[4]可能分成1+4,2,+3,3+2,4+1；计算比较1 * 4,2 * 3,3 * 2,4 * 1的大小，这样即可得出最大值。 优化：14和41是重复的，所以你第一个数字<=i/2，这样降重，省下一半的时间。另外，要和dp[i-1]比大小。 公式：f(n)=max(f(i)*f(n-i))
public class P96_CuttingRope { public static int maxCutting(int length){ if(length<2) return 0; if(length==2)return 1; if(length==3)return 2; int[] dp = new int[length+1]; dp[0]=0; dp[1]=1; dp[2]=2; dp[3]=3; int max = 0; int temp = 0; for(int i=4;i<=length;i++){ max = 0; for(int j=1;j<=i/2;j++){ temp = dp[j]*dp[i-j]; if(temp>max) max = temp; } dp[i] = max; } return dp[length]; } public static void main(String[] args){ for(int i=2;i<10;i++){ System.out.println("长度为"+i+"的最大值->"+maxCutting(i)); } } }贪心算法
1.贪心算法后续补充
