本文主要是介绍编程题：剪绳子，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：
给一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1且m>1，2 ≤ n ≤ 60），每段绳子的长度记为k[0],k[1],…,k[m-1]。请问k[0] * k[1] * … * k[m-1]可能的最大乘积是多少？例如，当绳子的长度是8时，把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
输入示例：
8
输出示例：
18
规定：
①输入给了一定范围：2 ≤ n ≤ 60。
②需要注意如果有多种剪法，那么输出剪法中最大的绳子长度乘积。
解题思路：
思路：本题主要考察对问题的划分和子问题的求解，适合采用贪心算法或者动态规划进行求解。
（1）贪心算法
百度百科：贪心算法
（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来最好的选择。也就是说，不从整体最优上加以考虑，所做出的是在某种意义上的局部最优解。需要注意的是贪心算法不是对所有问题都能得到整体最优解。对于一个具体问题，要确定它是否具有贪心选择的性质，我们必须证明每一步所作的贪心选择最终能得到问题的最优解。
研究题意，对于给定长度的绳子，剪成若干段，求能剪出的最大的乘积。画出表格研究规律：（注：因为绳子全部剪成1后乘积为1不可能最大，故表格中省略长度2以上所有全剪成1的组合。）
| 绳子原长度 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | … |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 所有剪法 | \ | \ | 1*1 | 1*2 | 1*3, 2*2, 2*1*1 | 1*4, 2*3, 2*2*1 | 1*5, 2*4, 3*3, 2*2*2, … | 1*6, 2*5, 3*4, 3*3*1, 3*2*2, … | 1*7, 2*6, 3*5, 4*4, 2*2*2*2, 3*3*3*2, … | 1*8, 2*7, 3*6, 4*5, 4*3*2, 3*3*3, 2*2*2*2*1, … | … |
| 最优剪法 | \ | \ | 1*1 | 1*2 | 2*2 | 3*2 | 3*3 | 3*2*2 | 3*3*2 | 3*3*3 | … |
| 乘积 | \ | \ | 1 | 2 | 4 | 6 | 9 | 12 | 18 | 27 | … |
可以发现，剪绳子这个问题中，可以先尽可能多的建成长度为3的小段，如果最后剩下的那段长度为1，则退一步将一根长度为3的小段拿出来和长度为1的合起来，重新切分成两根长度为2的小段，即2*2>3*1。
证明：当 n≥5 时，3(n-3)-n=2n-9>0，2(n-2)-n=n-4>0，1(n-1)-n=-1<0。因此在 n≥5 的情况下，将绳子剪成1比不剪更糟，将绳子剪成2或3均比不剪更好。又因为3(n-3)-2(n-2)=n-5≥0，所以剪成3比剪成2得到的乘积更大。另一方面若最后剩下长度为1的绳子，则有22>31，即将1和3合起来重新剪成2和2。这样最终保证乘积最大。
//贪心算法
#include <cmath>class Solution {
public:int cutRope(int number) {if(number<4){//2和3时单独考虑return number-1;}int cnt_3 = number/3;//绳子可以切成多少长度为3的段int rest = number%3;//将绳子全切分成3后剩下的长度int chengji = pow(3,cnt_3);//总的乘积if(rest==1){//剩余长度为1时chengji = chengji/3*4;//4=2*2,2*2>3*1}else{chengji *= rest;//剩余长度不为1时则直接相乘}return chengji;}
};
（2）动态规划方法
贪心算法只要确定可以通过找到最优子结构求解问题，那么实现起来会很简单。但实际上很多时候我们很难发现规律，更别说证明每一步的贪心选择使我们最终能得到问题的最优解，例如证明上述的“更多地剪成长度为3的小段会使得乘积更大”是有难度的。所以更通用的我们会考虑是否能采用动态规划来解决这一问题。
考虑这样一个问题，从n=4开始，每次的结果是否可以由其他小的已求出的结果得到呢？从方法（1）中的表格可以发现一定端倪，例如长度为6的绳子，它可以由长度为[2, 4]的绳子组合，也可以由长度为[3, 3]的绳子组合，还可以由长度为[1, 5]的绳子组合。进一步，2和4的绳子组合中，长度为4的绳子又可以由[1, 3]和[2, 2]组合，也就是说大的问题的解是可以通过已求出的更小问题的解得到的。
这里我们用数组dp[i]来保存长度为i的绳子各种剪法下的最大乘积，定义dp[1]=1，dp[2]=2，dp[3]=3。
| 绳子原长度i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | … |
|---|---|---|---|---|---|---|---|---|---|---|---|
| dp[i]=? | \ | dp[1]=1 | dp[2]=2 | dp[3]=3 | dp[1]*dp[3], dp[2]*dp[2] | dp[1]*dp[4], dp[2]*dp[3] | dp[1]*dp[5], dp[2]*dp[4], dp[3]*dp[3] | dp[1]*dp[6], dp[2]*dp[5], dp[3]*dp[4] | dp[1]*dp[7], dp[2]*dp[6], dp[3]*dp[5], dp[4]*dp[4] | dp[1]*dp[8], dp[2]*dp[7], dp[3]*dp[6], dp[4]*dp[5] | … |
| 最大乘积 | \ | 1 | 2 | 3 | 4 | 6 | 9 | 12 | 18 | 27 | … |
//动态规划
class Solution {
public:int cutRope(int number) {if(number<4){return number-1;}int dp[61];//动态规划数组dp[1] = 1;dp[2] = 2;dp[3] = 3;for(int i=4;i<=number;i++){//对dp[i]，依次拆分判断子元素乘积最大值int low = 1;int high = i-1;int max_cj = 0;//最大乘积while(low<=high){if(dp[low]*dp[high]>max_cj){max_cj = dp[low]*dp[high];}low++;high--;}dp[i] = max_cj;}return dp[number];}
};
输入输出测试：
测试用例1：
输入：
4
输出：
4
测试用例2：
输入：
12
输出：
81
这篇关于编程题：剪绳子的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
