剑指Offer(牛客版)--面试题14：剪绳子

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

1、动态规划(完整代码)：

/***************动态规划算法*****************/
#include<iostream>

using namespace std;

//求剪完绳子之后的最大乘积
int MaxProductAfterCutting_Solution(int length)
{
	//定义当绳长小于2时，最大的乘积
	if (length < 2)
		return 0;
	//当绳长等于2时，最大的乘积
	if (length == 2)
		return 1;
	//当绳长等于3时，最大的乘积
	if (length == 3)
		return 2;

	/*********下面考虑的是，剩下绳长的最大乘积***********/
	//当剩下的绳长分别是0/1/2的时候，最大乘积就是本身的长度，不需要再去剪,因为一刀没有不剪的乘积大
	int* product = new int[length + 1];
	product[0] = 0;
	product[1] = 1;
	product[2] = 2;
	product[3] = 3;

	//绳长的最大乘积
	int Max_Value = 0;

	/**********下面考虑的是当绳长大于等于4的时候，绳子的最大乘积***********/
	for (int i=4; i <=length; ++i)
	{ 
		//每次将最大乘积清空
		Max_Value = 0;
		
		//计算绳长为i时的最大乘积
		//因为要计算f(i)乘以f(i-j)的最大值，j超过一般是就重复
		for (int j =1; j <= i / 2; ++j)
		{
			int products = product[j] * product[i - j];

			//如果最大乘积比当前的最大值还要大
			if (Max_Value < products)
				//将绳长为i的最大乘积记录下来
				Max_Value =products;
		}
		//更新记录表中的最大乘积
		product[i] = Max_Value;
	} 

	//将绳长的最大的乘积记录下来
	 Max_Value = product[length];

	//删除辅助空间
	delete[] product;

	//返回绳长最大的乘积
	return Max_Value;
}



int main()
{
	//定义绳长
	int length = 9;

	//求最后的最大乘积
	int result = MaxProductAfterCutting_Solution(length);

	//输出最大的乘积
	cout << "此时得到的最大乘积是:"<<result << endl;
	return 0;

}
           

2、贪婪算法(完整代码）：

/*****************贪婪算法*****************/

#include<iostream>
using namespace std;

//求绳长的最大乘积
int MaxProductAfterCutting_Solution(int length)
{
	/******当绳长不超过3时的最大乘积******/
	//当绳长不超过2时的最大乘积
	if (length < 2)
		return 0;
	//当绳长为2时的最大乘积
	if (length == 2)
		return 1;
	//当绳长为3时的最大乘积
	if (length == 3)
		return 2;

	/*********当绳长超过5时，尽可能多地把绳子剪成长度为3**********/
	//绳长为3的绳子段数
	int timesof3 = length/3;

	/*当剩下的绳长恰好为4时，则不能再剪去3，最优的解释将绳长为4剪成2*2*/
	//如果剩下绳长为1
	if (length - timesof3 * 3 == 1)
		timesof3--;//留下一段长度为3的绳长
	
	//绳长为3的绳子段数
	int timesof2 = (length-timesof3*3) / 2;

	//绳子的最大乘积
	return pow(3, timesof3)*pow(2, timesof2);
}

int main()
{
	//定义绳长
	int length = 9;

	//获取绳长的最大乘积
	int result = MaxProductAfterCutting_Solution(length);

    //输出最后的结果
	cout << "此时绳长的最大乘积:" << result << endl;
	return 0;
}