切绳子啊啊啊

本文主要是介绍切绳子啊啊啊，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1、描述

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

示例 1：

输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1
示例 2:

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36

来源：力扣（LeetCode）
链接
参考答案
数据量更大的一个
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2、关键字

整数长度，剪成整数，段数未定。

3、思路

思路一：动态规划，
前面的直接写出来结果，后面如果用到dp也是从下标4之后才是统计的答案的。
思路二：数学中的均值不等式。按照长度3，一点一点的切分，
如果数字太大让取余，就多个位置多取几下
列举几下结果：
2只能分成 1 + 1
3 --> 2 + 1
4–> 2 + 2
5–> 3 + 2
6–> 3 + 3
7–> 3 + 2 + 2
8–> 3 + 3 + 2
可以看出能分成3，就不要分成2，观察可以看出来 5 这个是一个分界点。

4、notes

一开始就会觉着有很多种方式，但是肯定是最相近得到的乘积最大。

5、复杂度

时间：O(1)仅有求整、求余、次方运算,
资料提到不超过机器数的整数可以看作是 O(1)；
空间：O(1)

6、code

方法2：均值不等式

class Solution {
public:int cuttingRope(int n) {if(n <= 3) return n-1; // 2->1,3->2 , 4-> 4 , 5-> 6else if(n == 4) return 4;int res = 1;while(n >= 5){res *= 3;n -= 3;}return res * n;}
};另外一个更大的数字：
class Solution {
public:int cuttingRope(int n) {if(n < 4) return n-1;else if(n == 4) return 4;long res = 1;   // 这里int --> long while(n >= 5){res = res %1000000007;  // res *= 3;res = res %1000000007;  // n -= 3;}res = res * n;res = res %1000000007;  // return res;}
};

dp

class Solution {
public:int cuttingRope(int n) {if(n <= 3) return n-1; // 如果是小于等于3，就直接给出答案，vector<int> dp(n + 1, 1);dp[1] = 1;dp[2] = 2;dp[3] = 3;for(int i = 4; i <= n; i++){  // dp数组中存的答案是得等到dp[4]之后才是！前边几个都是为了计算后边的for (int k = 2; k < i  ; k++){  // 从线段长度大于等于2才切dp[i] = max(dp[i], dp[i - k] * dp[k]);  // 把当前值i,前面所有的结果都遍历一遍。}}return dp[n];}
};

这篇关于切绳子啊啊啊的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---