首页 > 试题广场 >

剪绳子

[编程题]剪绳子

热度指数：257477 时间限制：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 。

数据范围： $2 \le n \le 60$
进阶：空间复杂度 $O(1)$ ，时间复杂度 $O(n)$

输入描述:

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

输出描述:

输出答案。

示例1

输入

输出

说明

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

示例2

输入

输出

说明

m>1，所以切成两段长度是1的绳子

算法知识视频讲解

牛客题解官

发表于 2020-06-02 11:07:48

精华题解题目的主要信息：把一根长度为nnn的绳子分成mmm段，每段长度都是整数求每段长度乘积的最大值举一反三：学习完本题的思路你可以解决如下题目： JZ83. 剪绳子（进阶版） JZ71. 跳台阶扩展问题 JZ42. 连续子数组的最大和方法一：动态规划（推荐使用）知识点：动态规划动态规划算展开全文

数据结构和算法

发表于 2021-07-03 22:19:49

精华题解数学方式解决在做这题之前我们先来看这样一个问题，一个整数先把他分成两部分，x+y=n（假设x>=y并且x-y<=1,也就是说x和y非常接近）那么乘积是x*y。然后我们再把这两部分的差放大(x+1)+(y-1)=n(假设x>=y)；他们的乘积是（x+1）*(y-1)=x*y-(x- 展开全文

Maokt

发表于 2021-07-01 15:08:02

精华题解算法思想一：动态规划解题思路： 1、我们想要求长度为n的绳子剪掉后的最大乘积，可以从前面比n小的绳子转移而来 2、用一个dp数组记录从0到n长度的绳子剪掉后的最大乘积，也就是dp[i]表示长度为i的绳子剪成m段后的最大乘积，初始化dp[2] = 1 3、我们先把绳子剪掉第一段（长度为j 展开全文

Peterliang

发表于 2021-07-14 19:30:27

精华题解题意分析题目的意思是给出一个数字，让我们将这个数字进行分解，然后找到分解后所有的数的乘积最大的情况。样例分析，我们可以将8分解为2x3x3，得到的结果就是18,这个可以自己暴力枚举一下所有的情况进行验证。思路分析这个题目，我主要用的是三种方法进行解答解法一暴力枚举我们可以发现展开全文

leaves0924

发表于 2021-07-03 22:41:19

精华题解题目描述给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1，m<=n），每段绳子的长度记为k[1],...,k[m]。请问k[1]x...xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最展开全文

NumPy

发表于 2021-07-09 08:35:27

精华题解一、题目描述 JZ67 剪绳子题目描述：给一根长度为n的绳子，请把绳子剪成整数长度的m段（m、n都是整数，m>1），使得每段长度的乘积最大注意审题：m、n都是整数，剪出的绳子长度也是整数，因此不用考虑浮点数的情况，并且m要求大于1，即只要要剪成两段二、算法1（动态规划）解题思路将绳子分展开全文

牛一霸

发表于 2021-07-03 11:01:08

精华题解题目：剪绳子描述：给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1，m<=n），每段绳子的长度记为k[1],...,k[m]。请问k[1]x...xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三展开全文

qiaoHaoTing

发表于 2020-03-24 00:29:23

先来一个一般性问题：周长一定为n，这时候长length与宽width在什么情况下，达到面积s最大 s = length * width设length = x则：width = n/2 - x 所以 s = x * (n/2 - x) = -x^2 + n*x/2 求导s' = -2x + 展开全文

Oh~Sunny

发表于 2020-02-13 14:08:55

此题作为面试中经常考到的类型,涉及到我们熟悉的递归,动态规划,贪婪算法这三种,此文会介绍这三种解法. 递归我们先定义函数f(n)为把绳子剪成若干段之后的各段长度乘积的最大值.在剪第一刀的时候,我们会有n-1种可能的选择,也就是说剪出来的第一段绳子的长度可能为1,2,......n-1.因此就有了递展开全文