本文主要是介绍剪绳子（动态规划和贪婪算法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：
把长度为n的绳子剪成m段（n>1,m>1），每段绳子的长度记为k[1],...k[m]，则每段绳子的长度的最大乘积是多少？例如身子长度为8时，剪成2,3,3三段得到的乘积最大，为18。
思路：
方法1：动态规划的思想
假设长度为n的绳子被剪成若干段后，各段长度的最大乘积为f(n)。一刀下去可能的位置有1,2，...，n-1，j将绳子分为长度为i和n-i的两段，则f(n)=max{f(i)*f(n-i)}，i=1,2,...,n-1。从上往下递归时可能会有很多重复的计算，因此采用从下往上的方式，先计算f(2),f(3)，后面的就可以依次计算了。n=2时，只有一种剪法，f(2)=1*1=1，n=3时，只有剪成1,2，f(3)=1*2=2*1=2。
写代码要注意：n=2时，因为必须要剪一刀，只能剪成1和1，所以最大乘积是1，但是初始化f(2)的时候，是为了计算n>3的情况，因此如果有长度为2的肯定至少剪了一刀，这时候长度为2的最大乘积是2，初始化f(3)也是同理。
方法2：贪婪算法的思想
如果按照如下策略来剪绳子，则得到各段绳子的长度的乘积将最大。当n>=5时，尽可能多剪长度为3的绳子，当剩下绳子长度为4时，剪成2*2的两段。
写代码要注意：整除3后余数只有0,1,2三种情况，如果是2，那应该直接2*3^(timeOf3)；如果是1，说明多剪了一个3，应该应该拿出来一个3（timeOf3-1）和剩下的1组成4，结果是4*3(timeOf3)；如果是0，说明正好每段为3剪完，结果是1*3^(timeOf3)。
方法1代码：
int maxProduct(int n)
{if(n<=1)return 0;int *dp=new int[n+1];if(n==2)return 1;if(n==3)return 2;//注意这里的初始化dp[0]=0;dp[1]=1;dp[2]=2;dp[3]=3;for(int i=4;i<=n;i++){int maxP=0;for(int j=1;j<=i/2;j++){int product=dp[j]*dp[i-j];if(product>maxP)maxP=product;}dp[i]=maxP;}int result=dp[n];delete[] dp;return result;
}方法2代码：
int maxProduct(int n)
{if(n<=1)return 0;if(n==2)return 1;if(n==3)return 2;if(n==4)return 4;int timeOf3=n/3;int result=n-timeOf3*3;//余数//注意不同余数情况下的处理if(result==0)result=1;if(n-timeOf3*3==1){timeOf3-=1;result=4;}for(int i=1;i<=timeOf3;i++){result=result*3;}return result;
}
这篇关于剪绳子（动态规划和贪婪算法）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
