题目描述
给你一根长度为 n 绳子,请把绳子剪成 m 段(m、n 都是整数,2≤n≤58 并且 m≥2)。
每段的绳子的长度记为k[0]、k[1]、……、k[m]。k[0]k[1] … k[m] 可能的最大乘积是多少?
例如当绳子的长度是8时,我们把它剪成长度分别为2、3、3的三段,此时得到最大的乘积18。
样例
样例
输入:8
输出:18
在看到这道题时,我的第一反应就是动态规划
因为只有小于length的数剪出的值乘积最大可以推出到length拆开的数都是最大的
例如我们多推几个数
2--------1 1
3--------1 2
4--------1 3 或 2 2
5--------1 4 或 2 3
6--------1 5 或 2 4 或 3 3
7--------1 6 或 2 5 或 3 4
8--------1 7 或 2 6 或 3 5 或 4 4
由于最少都要剪2段,我就都让它由2段表示,而且可以肯定最大值就在这些组合中(因为这些数又可以拆除其他数)
2拆后的最大数为1
3可以拆除1 2
而2我们可以有两种情况
1. 2不动,也就是不拆
2. 2拆除最大,而2我们知道最大是1
这两种情况让我们知道,肯定是直接选2更合适,选择不拆
后面的数也是这样判断
我们判断的规则就是
本身的这个数 和 把这个数拆成最大值 相比较 看谁更大
谁更大我就选谁呗
C++ 代码
int f[60];
class Solution {
public:
int maxProductAfterCutting(int length) {
if(length == 2 || length == 3) return length - 1;
f[1] = 1;
f[2] = 1;
f[3] = 2;
for(int i = 4; i <= length; i++)
{
int a, b;
for(int j = 1; j <= i / 2; j++)
{
a = j;
b = i - j;
f[i] = max(f[i], a * b);
f[i] = max(f[i], a * f[b]);
f[i] = max(f[i], f[a] * b);
f[i] = max(f[i], f[a] * f[b]);
}
}
return f[length];
}
};