剑指offer之剪绳子问题
1 问题
给你一根长度为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.
2 分析
1) 分析边界值
n和m题目说了，要求大于1，所以绳子长度最少为2，而且每段的长度不能小于1。
当n=2的时候，我们只有一种分割方法，就是中间切断，变成了1*1 = 1，所以当绳子长度为2的时候，切断数长度乘积最大值为1
当n=3的时候，我们有2种分割方法，就是1*1*1 = 1,然后就是1*2 = 2，所以当绳子长度为2的时候，切断数长度乘积最大值为2
当n=4的时候，我们有3种分割方法，就是1*1*1*1 = 1,然后就是1*2 *1 = 2，还有2 * 2 = 4，所以当绳子长度为2的时候，切断数长度乘积最大值为4；
当n=5的时候，我们有4种分割方法，就是1*1*1*1*1 = 1,然后就是1* 2 *1 * 1 = 2，还有2 * 2 * 1 = 4，还有1 * 3 * 1 = 3，还有2 * 3 = 6;所以当绳子长度为2的时候，切断数长度乘积最大值为6；
我们记最大值为f(n)为长度为n绳子剪成若干段的最大乘积，我们可以知道f(n) = max{f(i) * f(n - i)}, i ∈ {1,2...,n - 1},
f(n)的最优解对应着f(i)和f(n-i)的最优解，假如f(i)不是最优解，那么其最优解和f(n-i)乘积肯定大于f(n)的最优解，然后f(i)又可以看成f(n),大问题包含小问题，并且大问题的最优解包含着小问题的最优解，所以可以使用动态规划求解问题.
-
f(4) = max{f(1) * f(3), f(2) * f(2)} = 4;
-
-
f(5)= max{f(1) * f(4), f(2) * f(3)} = 6;
-
-
...
-
-
f(n) = max{f(1) * f(n -1), ... , f(i) * f(n - i), ... }; 由于具有对称性，所以这里的i的范围是 i ∈ {1, 2..., n / 2};
3 代码实现
-
#include <stdio.h>
-
#include <stdlib.h>
-
-
int maxCutting(int len)
-
{
-
if (len <= 1)
-
{
-
return 0;
-
}
-
if (len == 2)
-
{
-
return 1;
-
}
-
if (len == 3)
-
{
-
return 2;
-
}
-
int *data = (int *)malloc(sizeof(int) * len + 1);
-
if (data == NULL)
-
{
-
printf("malloc data fail\n");
-
return 0;
-
}
-
data[0] = 0;
-
data[1] = 1;
-
data[2] = 2;
-
data[3] = 3;
-
int max;
-
for (int i = 4; i <= len; ++i)
-
{
-
max = 0;
-
for (int j = 1; j <= i / 2; ++j)
-
{
-
max = data[j] * data[i - j];
-
if (data[i] < max)
-
{
-
data[i] = max;
-
}
-
}
-
//printf("data[%d] is %d\n", i, data[i]);
-
}
-
return data[len];
-
free(data);
-
return 1;
-
}
-
-
int main(void)
-
{
-
int result = maxCutting(8);
-
if (!result)
-
{
-
printf("输入绳子长度不合法或者开辟数组内存失败\n");
-
return -1;
-
}
-
printf("绳子长度为8的最大切割乘积值为%d", result);
-
return 0;
-
}
4 运行结果
-
绳子长度为8的最大切割乘积值为18
-
5 总结
大问题包含小问题，并且大问题的最优解包含着小问题的最优解，所以可以使用动态规划求解问题.动态规划我们可以理解成高中数学知识的数列关系，既迭代，我们最关键的是找到迭代关系，如上题f(n) = max(f(i) * f(n -1));
文章来源: chenyu.blog.csdn.net，作者：chen.yu，版权归原作者所有，如需转载，请联系作者。
原文链接：chenyu.blog.csdn.net/article/details/101391438
- 点赞
- 收藏
- 关注作者
评论（0）