刷题笔记（十四）——剪绳子

题目描述

给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1而且m>1），每段绳子的长度记为k[0],k[1],...,k[m]。请问k[0]xk[1]x...xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，咱们把它剪成长度分别为二、三、3的三段，此时获得的最大乘积是18。code

示例1io

输入

复制class

8

输出

复制co

18

思路：题中没有限制拆分出数的数量，直观上看起来没有规律。1,2,3,4能够直接得出结果，接着考虑后面return

由于4只能拆成一、3和二、2，显然2*2较大，因此后面遇到4可直接拆成二、2

5：一、二、2；二、3；

6：一、5（再把5按上面的拆开）；二、二、2；三、3；

7：一、6（再把6按上面拆开）；二、5（再把5按上面的拆开）、三、二、2；

......

都是拆分红二、3

是三的倍数的话，直接所有拆成三，获得三的某次幂

不是三的倍数的话，先拆成三的倍数部分和余数部分，获得三的某次幂*余数（2或1）

class Solution {
public:
    int cutRope(int number) {
        if(number==1)return 1;
        else if(number==2) return 1;
        else if(number==3)return 2;
        else if(number==4)return 4;
        else
        {
            if(number%3==0)
            {
                int x=number/3;
                return pow(3,x);
            }
            else
            {
                int x=number/3;
                int y=number%3;
                return pow(3,x)*y;
            }
        }
    }
};