本文共 928 字，大约阅读时间需要 3 分钟。

剑指offer14 . 剪绳子 P96

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

动态规划， 令 f(n) 是长度n最后的最大乘积，剪在整数上i上 ，

int maxProduct(int length) {
   		if (length < 2)  return 0;   // 要求length > 1 	if (length == 2) return 1;   // 只能从i=1处剪 	if (length == 3) return 2;   // 同上 		int *dp = new int[length + 1];	memset(dp, 0, sizeof(dp)); // dp在前三个存的并不是答案，只是为了充当dp[i] 或 dp[n-i]，所以才在上面特判 // 因为n是1到3时，还必须要剪一刀，但是充当乘法因子不一定要在它们中间剪 	dp[1] = 1;  //前三个代表长度为i的子绳最大能提供的乘法因子是多少 	dp[2] = 2;	dp[3] = 3;	for (int i = 4; i <= length; ++i) {
       // i是绳长		for (int j = 1; j <= i / 2; ++j) {
   			dp[i] = max(dp[i], dp[j] * dp[i - j]);			//括号里的dp[i]存的是前几个j的dp[i]的最大值，跟当前比 		}	}    int ans = dp[length];    delete [ ] dp;	return ans; }

贪心那个解法已然放弃。。。我这样的学术辣鸡不配使用贪心。

转载地址：http://dhzzi.baihongyu.com/