首页 > 试题广场 >

剪绳子

[编程题]剪绳子
  • 热度指数：259956 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
给你一根长度为 n 的绳子，请把绳子剪成整数长的 m 段（ m 、 n 都是整数， n > 1 并且 m > 1 ， m <= n ），每段绳子的长度记为 k[1],...,k[m] 。请问 k[1]*k[2]*...*k[m] 可能的最大乘积是多少？例如，当绳子的长度是 8 时，我们把它剪成长度分别为 2、3、3 的三段，此时得到的最大乘积是 18 。

数据范围：
进阶：空间复杂度 ，时间复杂度

输入描述:
输入一个数n，意义见题面。


输出描述:
输出答案。
示例1

输入

8

输出

18

说明

8 = 2 +3 +3 , 2*3*3=18
示例2

输入

2

输出

1

说明

m>1，所以切成两段长度是1的绳子
算法知识视频讲解
查看答案及解析
添加回答
推荐
C/C++
天命剑主头像 天命剑主 
//
// Created by yuanhao on 2019-9-3.
//

#include <iostream>
#include <cmath>

using namespace std;

/**
 * 题目分析：
 * 先举几个例子，可以看出规律来。
 * 4 ： 2*2
 * 5 ： 2*3
 * 6 ： 3*3
 * 7 ： 2*2*3 或者4*3
 * 8 ： 2*3*3
 * 9 ： 3*3*3
 * 10：2*2*3*3 或者4*3*3
 * 11：2*3*3*3
 * 12：3*3*3*3
 * 13：2*2*3*3*3 或者4*3*3*3
 *
 * 下面是分析：
 * 首先判断k[0]到k[m]可能有哪些数字，实际上只可能是2或者3。
 * 当然也可能有4，但是4=2*2，我们就简单些不考虑了。
 * 5<2*3,6<3*3,比6更大的数字我们就更不用考虑了，肯定要继续分。
 * 其次看2和3的数量，2的数量肯定小于3个，为什么呢？因为2*2*2<3*3，那么题目就简单了。
 * 直接用n除以3，根据得到的余数判断是一个2还是两个2还是没有2就行了。
 * 由于题目规定m>1，所以2只能是1*1，3只能是2*1，这两个特殊情况直接返回就行了。
 *
 * 乘方运算的复杂度为：O(log n)，用动态规划来做会耗时比较多。
 */
long long n_max_3(long long n) {
    if (n == 2) {
        return 1;
    }
    if (n == 3) {
        return 2;
    }
    long long x = n % 3;
    long long y = n / 3;
    if (x == 0) {
        return pow(3, y);
    } else if (x == 1) {
        return 2 * 2 * (long long) pow(3, y - 1);
    } else {
        return 2 * (long long) pow(3, y);
    }
}

//给你一根长度为n的绳子，请把绳子剪成m段（m、n都是整数，n>1并且m>1），每段绳子的长度记为k[0],k[1],...,k[m]。请问k[0]xk[1]x...xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
//
//输入描述:
//输入一个数n，意义见题面。（2 <= n <= 100）
//
//
//输出描述:
//输出答案。
//示例1
//输入
//8
//输出
//18
int main() {
    long long n = 0;
    cin >> n;
    cout << n_max_3(n) << endl;
    return 0;
}

编辑于 2021-07-06 10:46:45 回复(61)
Jiaye-DUT头像 Jiaye-DUT

python解法：动态规划
带备忘录的动态规划： : 

    def cutRope(self, number):
        # write code here
        if number == 0:
            return 0
        elif number in (1,2):
            return 1
        elif number == 3:
            return 2
        return self.subFunction(number)

    def subFunction(self, number):
        tempL = [0]*(number+1)
        tempL[0] = 1
        maxV = 0
        if tempL[number] != 0:
            return tempL[number]
        for i in range(1, number+1):
            ans = i*self.subFunction(number-i)
            if ans>maxV:
                maxV = ans
                tempL[number] = maxV
        return maxV
编辑于 2019-09-05 20:38:02 回复(5)
Java
内推抖音Robot头像 内推抖音Robot
小伙砸，来一手动态规划吧，简单易懂哟~ 
public class Solution {
    public int cutRope(int target) {
        int[] dp = new int[61];
        dp[0] = -1;
        dp[1] = 1;
        dp[2] = 1;
        for(int i=3;i<=target;i++){
            int res = 0;
            for(int j=1;j<=i/2;j++){
                int a = Math.max(dp[j],j);
                int b = Math.max(dp[i-j],i-j);
                if(a * b > res){
                    res = a * b;
                }
            }
            dp[i] = res;
        }
        return dp[target];
    }
}


发表于 2020-03-21 22:52:00 回复(1)
C++
勇敢牛牛，不怕困难！头像 勇敢牛牛，不怕困难！ 
class Solution {
public:
  // Dynamic Programming (Bottom-Up)
  int cutRope(int number) {
    vector<int> dp(number + 1);
    dp[1] = dp[2] = 1;
    
    for (int i = 3; i <= number; ++i)
      for (int j = 1; j <= i - 1; ++j)
        // 状态转移方程
        dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]));
    
    return dp.back();
  }

  // 解法2 -- 记忆化递归 (Top-Down)
  int cutRopeII(int number) {
    memo_.resize(number + 1);
    return cut(number);
  }
  
private:
  vector<int> memo_;
  
  int cut(int n) {
    if (n <= 2)
      return 1;
    
    if (memo_[n] > 0)
      return memo_[n];
    
    int ans = 1;
    for (int i = 1; i <= n - 1; ++i)
      ans = max(ans, max(i * (n - i), i * cut(n - i)));
    
    return memo_[n] = ans;
  }
  
};

发表于 2021-10-09 13:03:50 回复(0)
Python
w_w_头像 w_w_

python动态规划\贪婪算法

# -*- coding:utf-8 -*-
class Solution:
    def cutRope(self, number):
        # write code here
        #动态规划，自下向上解决问题
        if number < 2:
            return 0
        if number == 2:
            return 1
        if number == 3:
            return 2
        #保存结果的数组，
        result = [0,1,2,3]
        for i in range(4, number+1):
            max = 0
            for j in range(1,i/2+1):
                temp = result[j]*result[i-j]
                if temp > max:
                    max = temp
            result.append(max)
        return result[number]

# -*- coding:utf-8 -*-
class Solution:
    def cutRope(self, number):
        # write code here
        #贪婪算法
        if number < 2:
            return 0
        if number == 2:
            return 1
        if number == 3:
            return 2
        if number == 4:
            return 4
        result = [0,1,2,3,4]
        num3 = number/3
        num2 = 1
        if number-num3*3 == 1:
            num3 -= 1
            num2 = 1
        return pow(3,num3) * pow(2,num2)



编辑于 2020-06-22 10:59:35 回复(0)
我是真的菜得1P头像 我是真的菜得1P
动态规划，几行搞定~ 
public class Solution {
    public int cutRope(int target) {
        int dp[]=new int[target+1];
        dp[0]=1;
        for(int i=1;i<=(target+1)/2;i++){
            for(int j=i;j<=target;j++){
                dp[j]=Math.max(dp[j],dp[j-i]*i);
            }
        }
        return dp[target];
    }
}


发表于 2020-04-06 16:43:44 回复(0)
ML_ZDD头像 ML_ZDD 
class Solution {
public:
    int cutRope(int number) {
        if(number < 2)
            return 0;
        if(number == 2)
            return 1;
        if(number == 3)
            return 2;
        vector<int> res(number + 1, 0);
        res[1] = 1;
        res[2] = 2;
        res[3] = 3;
        int max_length = 0;
        for(int i = 4; i <= number; ++i)
        {
            for(int j = 1; j <= i / 2; ++j)
            {
                if(res[i - j] * j > max_length)
                    max_length = res[i -j] * j;
            }
            res[i] = max_length;
            max_length = 0;
        }
        return res[number];
    }
};
动态规划，当绳子长度大于等于4的时候，不管对绳子割几刀，总可以把问题看成，先割一刀（长度在1-n）之间，考虑对称性第一刀范围在1-n/2之间
发表于 2020-02-02 11:01:35 回复(0)
蘑菇菌头像 蘑菇菌
数学归纳法： 
# -*- coding:utf-8 -*-
class Solution:
    def cutRope(self, number):
        # write code here
        if number == 2:
            return 1
        if number == 3:
            return 2
        if number == 4:
            return 4
        count = 1
        while count*3<number:
            count += 1
        count -= 1
        k = number-count*3
        return k*(3**count)


发表于 2019-10-03 21:48:21 回复(1)
灿烂ll人生头像 灿烂ll人生 
class Solution {
public:
    int cutRope(int number) {
        vector<int>dp(number+1,1);
        for(int i=1;i<=number;i++){
            for(int j=1;j<=i;j++){
                dp[i]=max(dp[i],dp[i-j]*j);
            }
        }
        return dp[number];
    }
};
看到题目的第一瞬间，就想到了动态规划，不难想到动态规划方程为dp[i]=max(dp[i],dp[i-j]*j);其中j<=i;这是重点，举个例子，8的最大乘积，dp[8]=max(dp[8],dp[8-1]*1),而dp[8]=max(dp[?],dp[8-2]*2)........依次判断，得出来的就是最终答案。

编辑于 2020-07-05 21:59:02 回复(0)
C/C++
Jonnnnnnnnnnn头像 Jonnnnnnnnnnn
记录一下菜鸡题解
首先想到的是用递归的方法，看了评论以后才想到动态规划更好一些，果然自己对东台规划的问题理解的不够
虽然题目不要求，但为了调试方便，列出了所有res的情况 

class Solution {
public:
int cutRope(int number, vector<int>k, int temp, vector<vector<int>> &res,int &_max)
{
	if (number <= 3)
	{
		k.push_back(number);
		res.push_back(k);
		temp *= number;
		_max = max(_max, temp);
		return _max;
	}
	for (int i = 2; i <= number/2; ++i)
	{
		k.push_back(i);
		cutRope(number - i, k, temp*i, res,_max);
		k.pop_back();
	}
	return _max;
}

int cutRope(int number) {
	vector<vector<int>> res;
	if (number <= 2)
		return 1;
	if (number == 3)
		return 2;
	vector<int>k;
	int _max = 0;
	cutRope(number, k, 1, res,_max);
	return _max;
}

};


发表于 2019-09-16 10:38:04 回复(0)
C++
Spectre_头像 Spectre_ 
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型
     */
    int cutRope(int n) {
        // 贪心，时间复杂度O(N)，空间复杂度O(1)
        if (n < 4) return n - 1;
        int res = 1;
        while (n > 4) {
            res *= 3;
            n -= 3;
        }
        return res * n;
    }
};

发表于 2022-08-14 00:00:50 回复(0)
Python 3
撒旦法说头像 撒旦法说 
class Solution:
    def cutRope(self , number: int) -> int:
        # write code here
        l=[]
        for i in range(2,number+1):
            x=number//i
            lf=number-x*i
            res=x**(i-lf)*(x+1)**lf
            l.append(res)
        return max(l)

发表于 2021-12-23 21:53:09 回复(0)
Java
陈明燊头像 陈明燊
公式+快速幂 
public class Solution {
    public int cutRope(int target) {
        if(target==2||target==3)return target-1;
        if(target%3==0)return qpow(3,target/3);
        else if(target%3==1)return 4*qpow(3,(target-4)/3);
        else return 2*qpow(3,(target-2)/3);
    }
    int qpow(int base,int exp){
        int ret = 1;
        while (exp>0){
            if ((exp & 1)==1)ret*=base;
            base*=base;
            exp >>= 1;
        }
        return ret;
    }
}


发表于 2021-11-14 13:18:19 回复(0)
C++
offer马到成功头像 offer马到成功 


// 解法采用，多3少2无1的方法 class Solution {
public:
    int cutRope(int number) {
        int a = number / 3;
        int b = 0;
        if(number % 3 ) b = number % 3;
        int ret = 0;
        if(b == 1) ret = pow(3, a-1)* 4;
        else ret = b > 0 ? pow(3, a) * b : pow(3, a);
        
        return ret;
    }
        
        
}; 

发表于 2021-09-19 18:11:34 回复(0)
C++
Shallkon头像 Shallkon 
class Solution {
public:
    int cutRope(int number) {
        if (number == 2) {
            return 1;
        }
        else if (number == 3) {
            return 2;
        }

        vector<int> f(number, -1);
        for (int i = 0; i < 4; ++i) {
            f[i] = i + 1;
        }
        for (int i = 4; i < number; ++i) {
            for (int j = 0; j < i; ++j) {
                f[i] = max(f[i], j * f[i - j]);
            }
        }
        return f[number - 1];
    }
};

发表于 2021-07-19 23:15:39 回复(1)
小桥流水少年梦头像 小桥流水少年梦 
    public int cutRope(int target) {
        if(target < 3){
            return target - 1;
        }
        
        int res = 1 ;
        while( target > 4){
            res *= 3;
            target -= 3;
        }
        return target * res;
    }

发表于 2021-07-08 15:24:03 回复(0)
Java
酸辣毛小豆头像 酸辣毛小豆 
import java.util.*;
public class Solution {
    public int cutRope(int target) {
        //找规律：三种情况
        // 5 = 3*2；  3^(5/3)*2;
        // 6 = 3*3;   3^(6/3);
        // 7 = 3*2*2;  3^(7/3-1)*2;
         if(target==2){
            return 1;
        }
        if(target==3){
            return 2;
        }
        if(target==4){
            return 4;
        }
        int index = (target-5) % 3;
        if(index == 0)return (int)Math.pow(3,target/3)*2;
        if(index == 1)return (int)Math.pow(3,target/3);
        return (int)Math.pow(3,target/3-1)*4;
       
    }
    
 
}

发表于 2021-03-19 17:17:45 回复(0)
JavaScript
IPzzzi头像 IPzzzi 
function cutRope(number)
{
    // write code here
    var arr = [2,3,4,6,9,12];
    var a = Math.floor((number - 2) / 6);
    var b = number - a * 6 - 2;
    if(a == 0){
        return arr[b];
    }
    var sum = arr[b];
    for(var i = 0;i < a;i++){
        sum *= 9;
    }
    return sum;
}
找规律，2-7是[2,3,4,6,9,12]，接下来的数以6为一个周期循环，每个周期对应数组里面的数乘上9，例如15，是第3排，第2个数，对应第一排的3，就等于3 * 9 * 9 = 243
发表于 2021-03-19 16:13:43 回复(0)
Java
浅羊头像 浅羊

思路

首先，根据中学知识就能知道，尽可能分成等长的时候乘积最大。

中学时有这种题:
把长为a的线段分成两段，问两段的长度分别是多少时，才能使得以这两段分别作为长、宽所得到的矩形面积最大？
结论是对半分时最大。记得当时老师类推过分成m份，也是等分时乘积最大。
也就是求f(x)=(x)^(n/x)的最大值。

高数学的导数指数什么的忘了挺多，但可以笨办法算：
等分后要么都是2，要么都是3（4以上可以继续分），随便找个数n=6，就知道分成3更大。
接下来尽可能分成3即可。

代码

    public int cutRope(int target) {
        int res = 1;
        for (int i = target / 3; i > 0; i--) res *= 3;
        if (target % 3 == 2) res *= 2;
        if (target % 3 == 1) res = res / 3 * 4;
        return res;
    }
发表于 2021-02-23 16:15:04 回复(0)
MrBear头像 MrBear 
 public int cutRope(int target) {
        int[] tmp = new int[61];
        tmp[2] = 1;
        for(int i=3;i<61;i++){
            int maxValue = 1;
            for(int j=1;j<i;j++){
                int l = Math.max(j,tmp[j]);
                int r = Math.max(i-j,tmp[i-j]);
                maxValue = Math.max(l*r,maxValue);
            }
            tmp[i] = maxValue;
        }
        return tmp[target];
    }

发表于 2021-02-01 16:46:01 回复(0)
牛客625718772号头像 牛客625718772号
只用一行代码：
return number%3==1?pow(3,number/3-1)*4:pow(3,number/3)*((number%3)/2+1);

发表于 2021-01-05 02:51:59 回复(0)
提交观点

问题信息

基础数学
上传者：小小
难度：
524条回答 69492浏览

热门推荐

通过挑战的用户

查看代码

相关试题

剪绳子

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号