一、题目描述

JZ67 剪绳子
题目描述：给一根长度为n的绳子，请把绳子剪成整数长度的m段（m、n都是整数，m>1），使得每段长度的乘积最大
注意审题：m、n都是整数，剪出的绳子长度也是整数，因此不用考虑浮点数的情况，并且m要求大于1，即只要要剪成两段

二、算法1（动态规划）

解题思路

  1. 将绳子分割的最优方案可以从比他短的绳子的最优最优方案中推出来，因此我们可以想到用动态规划来解决本题
  2. 将绳子的长度作为状态，定义数组f[x]表示将长度为x的绳子分割成至少两段所能得到的最大乘积，假设已知f[2~x-1]的结果，那么我们可以枚举切出的第一段的长度j，故需考虑两种方案：
  • 将x拆分为j和(x - j)这两段，且(x - j)不再继续拆分
  • 将x拆分为j和(x - j)这两段，(x - j)继续拆分，最大值为f[x - j]

由于至少剪成两段故j的取值范围是[1, x)，根据题意f[0] = f[1] = 0
故状态转移方程如下：

代码实现（C++11）

class Solution {
public:
    int cutRope(int number) {
        vector<int> f(number + 1);
        f[2] = 1;
        for(int i = 3; i <= number; i++){
            for(int j = 1; j < i; j++){    // 枚举剪下的第一段绳子的长度j
                f[i] = max(f[i], max(j * (i - j), j * f[i - j]));
            }
        }
        return f[number];
    }
};

时间复杂度：O(n^2)，n为number，每次枚举剪下的第一段的长度，故时间复杂度为O(n^2)
空间复杂度：O(n)，f数组所用空间

三、算法2（数学）

解题思路

  1. 通过数学证明，可以得到一个结论：当绳子的总长度大于3时，剪出的绳子中长度为2的至多2段，其余的都是长度为3的绳子
  2. （1） 当绳子长度 x <= 3时，最大乘积为 x - 1
    （2） 当绳子长度 x == 4时，可以分为2 * 2两段
    （3） 当绳子长度 x >= 5时，把x拆分为3 + (x - 3)，那么3 * （x - 3） = 3 * x - 9 显然 3 * x - 9 > x 成立，即将一段大于等于5的绳子剪出一段长度为3的绳子，总会使得乘积变大，把x拆分为2 + (x - 2)，那么2 * （x - 2） = 2 * x - 4 显然 2 * x - 4 > x 也成立，若剪出4则可以再剪出两个2，故剪出的长度只含2、3。当x == 5时，显然分为2和3最优；当x > 5时，由于3 * 3 > 2 * 2 * 2，故每出现3个2时，我们总能将其替换为两个3使得乘积变大，故剪出的绳子中长度为2的至多2段
  3. 故我们可以先求x对3的余数，根据余数分情况讨论，当然（x >= 4）：
    （1） 若余数为0：即x可以被3整数，答案为 pow(3, x / 3)
    （2） 若余数为1：故需先切两段长度为2的绳子，答案为 4 * pow(3, (x - 4) / 3)
    （3） 若余数为2：故需先切一段长度为2的绳子，答案为 2 * pow(3, (x - 2) / 3)

代码实现（C++11）

class Solution {
public:
    int qmi(int a, int b){
        int res = 1;
        while(b){
            if(b & 1) res *= a;
            a *= a;
            b >>= 1;
        }
        return res;
    }

    int cutRope(int number) {
        if(number <= 3) return number - 1;
        int remainder = number % 3;
        if(remainder == 0) return qmi(3, number / 3);
        else if(remainder == 1) return 4 * qmi(3, (number - 4) / 3);
        return 2 * qmi(3, (number - 2) / 3);
    }
};

时间复杂度：O(logn)，快速幂的时间复杂度是log级别的
空间复杂度：O(1)，常数空间