题解 | #剪绳子#

剪绳子

http://www.nowcoder.com/practice/57d85990ba5b440ab888fc72b0751bf8

题目：剪绳子

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

输入描述：输入一个数n，意义见题面。（2 <= n <= 60）

返回值描述：输出答案。

示例1：输入：8，返回值：18

解法一：

思路分析：我们可以首先定义函数f(n)为把长度为n的绳子剪成若干段后乘积的最大值，则f(n) = max(f(i) - f(n - i))，将长度为n的绳子剪成长度为i和长度为n - i的两端，然后再进行子问题的求解。

实例分析：当number的值小于等于4的时候，表示长度不分得到的结果值最大。

tab[0] = 0;tab[1] = 1;tab[2] = 2;tab[3] = 3;

主要围绕这四个数据进行问题的求解，首先设定两个指针i和j，令i的值为初始值4，j的值为初始值1，i每递增1个单位值，j在i/2的范围内递增1个单位值。然后进行tab[i] = tab[j] * tab[i - j];的判断。

当输入的number值为8时，进行以下分析：

初始数值	tab[0] = 0	tab[1] = 1	tab[2] = 2	tab[3] = 3
number = 8	当i等于4，j等于1时，tab[j] * tab[i - j] = 3，最大值变为3
	当i等于4，j等于2时，tab[j] * tab[i - j] = 3，最大值变为4
i = 5	j等于1时，tab[j] * tab[i - j] = 4
	j等于2时，tab[j] * tab[i - j] = 6
i = 6	j等于1时，tab[j] * tab[i - j] = 6
	j等于2时，tab[j] * tab[i - j] = 8
	j等于3时，tab[j] * tab[i - j] = 9
i = 7	j等于1时，tab[j] * tab[i - j] = 9
	j等于2时，tab[j] * tab[i - j] = 12
	j等于3时，tab[j] * tab[i - j] = 12
i = 8	j等于1时，tab[j] * tab[i - j] = 12
	j等于2时，tab[j] * tab[i - j] = 18
	j等于3时，tab[j] * tab[i - j] = 18

下面C++代码为：

class Solution {
public:
    int cutRope(int number) {
        if(number <= 4)//特殊情况
            return number;
        else{
            int *tab = new int[number + 1];//表格数组
            int i,j;
            //填表过程
            tab[0] = 0;
            tab[1] = 1;
            tab[2] = 2;
            tab[3] = 3;
            for(int i = 4; i <= number;i++){
                tab[i] = 0;
                for(int j = 1; j <= i/2;j++){
                    if(tab[i] < tab[j] * tab[i - j])//判断最大值
                        tab[i] = tab[j] * tab[i - j];
                }
            }
            return tab[number];
        }
    }
};

因为里面有两层嵌套循环，故时间复杂度为O(n^2)，空间复杂度为O(1)。

解法2：

思路分享：根据上述暴力法分析，我们可以得出大致的几个数据，就是当number < 5时，返回值皆为number，当numbe大于5时，如果能够对3进行整除，则最大值满足pow(3, number/3 - 1)*4，其他情况下满足pow(3, number/3) * pow(2, (number%3)/2)。由此我们可以得出简单的数学公式法计算结果。

具体C++程序分析：

class Solution {
public:
    int cutRope(int number) {
        if(number < 5)//特殊情况
            return number;
        if(number % 3 == 1)//对3整除
            return pow(3, number/3 - 1)*4;
        else//其他情况满足
            return pow(3, number/3) * pow(2, (number%3)/2);
    }
};

因为采用数学公式法直接进行计算，所以时间复杂度为O(1)，空间复杂度O(1)。

算法自然分析文章被收录于专栏

在解决问题的同时，不断与人交流学习，通过牛客各式各样的题目，学习分享。