剑指offer编程题—剪绳子

题目描述
给你一根长度为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 <= 60）
输出描述:
输出答案。
示例
输入：8
输出：18

解题思路直接放在代码注释了。

/*题目描述
给你一根长度为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。
*/
#include <iostream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;

//解题思路1：注意题目要求中的细节（m>1），即对于给定的绳子必须要剪成至少2段。
/*基本思想：这题感觉就是在找规律。用result数组记录对应长度的最大乘积，例如result[i]表示绳长为i时可能的最大乘积.
因为绳子剪裁后的段数必须大于1，所以绳长为2时，只能剪成长度为1的两段，所以result[2]=1*1,同理绳长为3时，只能剪成长度
为1和2的两段，因此result[3]=1*2.后面的依次类推，结果如下：
result[4]=2*2=4;
result[5]=2*3=6;
result[6]=3*3=9;
result[7]=2*2*3=12;
result[8]=2*3*3=18;
result[9]=3*3*3=27;
result[10]=2*2*3*3=36;
从上面的一系列推理可以看出，从result[7]开始后面的一系列都可以从前面的结果推出。
当n>=7时，result[i]=3*result[i-3];
*/
class Solution1 {
public:
    int cutRope(int number) {
        vector<int> result(number+6,0);
        result[1]=1;
        result[2]=1;
        result[3]=2;
        result[4]=4;
        result[5]=6;
        result[6]=9;
        for(int i=7;i<=number;++i){
            result[i]=3*result[i-3];
        }
        return result[number];
    }
};

//Solution1的优化方案
/*基本思想：从Solution1的推理过程中不难发现，k[0],k[1],...,k[m]中可能出现的数字只有2和3，也就是对于给定的绳长n，
当把绳子剪成x段长度为2的子段和y段长度为3的子段时，result[n]=result[2x+3y]=(2^x)*(3^y),要想乘积最大，要使长度为
3的子段尽量多，也就是y尽量大。
因此存在以下关系：对于给定绳长number，
y=number/3; 此时y最大
x=number%3; x=0 or 1 or 2;
x=0 说明子段的长度全部为3；
x=1 需要拿出一个长度为3的子段拼成长度为4的子段，也就是两个长度为2的子段
x=2 在剪出尽量多长度为3的子段后，最后剩余长度为2的子段，刚好。

其实这里对应一个数学定理，并且可以证明：
大数字都可以被拆分为多个2与3的和，以获取最大的乘积，只有2和3不需要拆分
网友证明链接：https://zhuanlan.zhihu.com/p/108832910
*/
class Solution2 {
public:
    int cutRope(int number) {
        if(number==2) return 1;
        if(number==3) return 2;
        int remainder=number%3; //余数
        int quotient=number/3; //商，也就是绳长可以剪成多少段长度为3的子段
        if(remainder==0) return pow(3,quotient);
        else if(remainder==1) return 4*pow(3,(quotient-1)); //余数为1则拿出一个3拼成4.
        else return 2*pow(3,quotient);
    }
};

//允许绳子的段数为1，即m>=1时的解决方案，这里与题目要求不同，可以存在不剪的情况，对应result[i]=i。
/*基本思想：自底向上的动态规划，动态规划算法的核心是记住已经已经求过的子问题的解。大概流程分三大步骤：
1.定义数组含义。这个数组用来记住已经求得的子问题解，在该题中，数组result记录对应绳长的最大乘积，
例如result[i]表示绳长为i，经过剪裁之后各子段的最大乘积，也就是说result[i]对应绳长为i时剪裁的最优解；
2.找出数组元素之间的关系式，也就是动态规划算法中常说的状态转换方程，在该题中，自顶向下分析有:对于
给定绳长n，将其分成长度为i和n-i的两段，则result[n]=result[i]*result[n-i],1<=i<n。 result[n-i]为
子问题的最优解，最终数组元素之间的关系为：result[n]=max{result[n],result[i]*result[n-i]},1<=i<n.
3.寻找初始值。有了数组元素之间的关系式，还得知道初始值才能自底向上求解。该题的初始值如下：
result[0]=0;
result[1]=1;
result[2]=2;
result[3]=3;
也就是绳长为1、2、3时，不剪对应的解为最优
剩下的可以由关系式推出，例如
result[4]=max{4,result[1]*result[3],result[2]*result[2]}
result[6]=max{6,result[1]*result[5],result[2]*result[4],result[3]*result[3],result[4]*result[2],result[5]*result[1]}
可以发现，上面有很多重复的计算，所以在利用子问题的最优解构建原问题的最优解时，只用遍历到i/2.
*/
class Solution3 {
public:
    int cutRope(int number) {
        vector<int> result(number+1,0);
        for(int i=1;i<=number;++i){
            result[i]=i;  //不剪
            //子循环中利用关系式和已求得的子问题的最优解来求解当前最优解，最终构造原问题的最优解
            for(int j=1;j<=i/2;++j){
                result[i]=max(result[i],result[j]*result[i-j]);
            }
        }
        return result[number];
    }
};
 //利用Solution2中的数学定理：一个大数可以拆分为多个2和3的和，以获取最大的乘积，只有2和3不需要拆分。
class Solution4 {
public:
    int cutRope(int number) {
        if(number==2) return 2;
        if(number==3) return 3;
        int remainder=number%3;
        int quotient=number/3;
        if(remainder==0) return pow(3,quotient);
        if(remainder==1) return 4*pow(3,(quotient-1));
        else return 2*pow(3,quotient);
    }
};
int main() 
{
    int n;
    cin>>n;
    Solution1 sol1;
    int res=sol1.cutRope(n);
    cout<<"Solution1:"<<res<<endl;

    Solution2 sol2;
    res=sol2.cutRope(n);
    cout<<"Solution2:"<<res<<endl;

    Solution3 sol3;
    res=sol3.cutRope(n);
    cout<<"Solution3:"<<res<<endl;

    Solution4 sol4;
    res=sol4.cutRope(n);
    cout<<"Solution4:"<<res<<endl;
    return 0;
}