剑指14：剪绳子

传送门

nowcoder
leetcode

题目描述

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

C++ 代码 - nowcoder

/*
    举例子，观察规律：
    4  ： 2*2
    5  ： 2*3
    6  ： 3*3
    7  ： 2*2*3 或 4*3
    8  ： 2*3*3
    9  ： 3*3*3
    10 ： 2*2*3*3 或 4*3*3

    分析：
    1.首先判断 k[0] ~ k[m] 可能有哪些数字，实际上只可能是 2 或 3。
    2.其次看 2 和 3 的数量，2 的数量肯定小于 3 个。如，2*2*2 < 3*3。
    3.直接用 n 除以 3，根据得到的余数判断有几个 2（0 或 1 或 2）。
    4.题目规定 m > 1，2 = 1*1，3 = 2*1，这两个特殊情况直接返回。

    时间复杂度：O(1)
    空间复杂度：O(1)
*/
class Solution {
public:
    int cutRope(int n) {
        if (n == 2) return 1;
        if (n == 3) return 2;

        int threeNums = n / 3;
        if (n - threeNums * 3 == 1)
            threeNums -= 1;
        int twoNums = (n - threeNums * 3) / 2;
        return pow(3, threeNums) * pow(2, twoNums);
    }
};

/*
    dp[i]：表示长度为 i 的绳子能拆分的最大乘积
    任取长度为 i 的绳子，最多可以切 i-1 刀，
    现在考虑切的第一刀，有 i-1 种切法
    那么，dp[n] = max(dp[i]*dp[n-i]), i取[1, n-1]

    时间复杂度：O(n^2)
    空间复杂度：O(n)
*/
class Solution {
public:
    int cutRope(int n) {
        if (n <= 3) return n - 1;

        vector<int> f(n + 1, 0);
        f[0] = 1, f[1] = 1, f[2] = 2, f[3] = 3;
        for (int i = 4; i <= n; i ++) {
            for (int j = 1; j <= i / 2; j ++) {
                f[i] = max(f[i], f[j] * f[i - j]);
            }
        }
        return f[n];
    }
};

C++ 代码 - leetcode

class Solution {
public:
    int cuttingRope(int n) {
        if (n == 2) return 1;
        if (n == 3) return 2;

        int threeNums = n / 3;
        if (n - threeNums * 3 == 1) threeNums -= 1;
        int twoNums = (n - threeNums * 3) / 2;
        return pow(3, threeNums) * pow(2, twoNums);
    }
};

class Solution {
public:
    int cuttingRope(int n) {
        if (n <= 3) return n - 1;

        vector<int> f(n + 1, 0);
        f[0] = f[1] = 1;
        f[2] = 2, f[3] = 3;
        for (int i = 4; i <= n; i ++) {
            for (int j = 1; j <= i / 2; j ++) {
                f[i] = max(f[i], f[j] * f[i - j]);
            }
        }
        return f[n];
    }
};