算法与数据结构

题目描述

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

由于答案过大，请对 998244353 取模。

思路 & 解答

这道题其实如果不是数值很大，我们可以使用动态规划来完成：

每个长度的绳子，要么最长的情况是不剪开（长度是本身），要么长度是剪开两段的乘积。因此每个长度length都需要遍历两个相加之后等于length的乘积，取最大值。

初始化值长度为1的值为1，从长度为2开始，每一种长度都需要遍历两个子长度的乘积。

public class Solution {
    public int cutRope(int target) {
        if (target <= 1) {
            return target;
        }
        int[] nums = new int[target + 1];
        nums[1] = 1;
        nums[0] = 1;
        for (int i = 2; i <= target; i++) {
            int max = i;
            for(int j=0;j<=i/2;j++){
                int temp = nums[j]*nums[i-j];
                if(temp>max){
                    max = temp;
                }
            }
            nums[i]=max;
        }
        return nums[target];
    }
}

C++ 代码如下：

class Solution {
public:
    int cutRope(int target) {
        if (target <= 1) {
            return target;
        }
        int[]
        nums[target + 1];
        nums[1] = 1;
        nums[0] = 1;
        for (int i = 2; i <= target; i++) {
            int max = i;
            for (int j = 0; j <= i / 2; j++) {
                int temp = nums[j] * nums[i - j];
                if (temp > max) {
                    max = temp;
                }
            }
            nums[i] = max;
        }
        return nums[target];
    }
};

但是由于数值比较大，直接乘积的时候就溢出了，我们仔细观察就会发现：

要想乘积比较大，在没有1的前提下，优先使用3，如果出现1，那么优先使用2 比如：

2 =  1 + 1
3 = 1 + 2
4 = 2 + 2
5 = 2 + 3
6 = 3 + 3
7 = 3 + 2 + 2
8 = 3 + 3 + 2
9 = 3 + 3 + 3
10 = 3 + 3 + 2 + 2
11 = 3 + 3 + 3 + 2
12 = 3 + 3 + 3 + 3

实现代码如下：

public class Solution {
    public long cutRope (long number) {
        if (number == 2) return 1;
        if (number == 3) return 2;
        long res = 1;
        while (number > 4) {
            res *= 3;
            res = res % 998244353;
            number -= 3;
        }
        return res * number % 998244353;
    }
}

结果很不幸：运行超时:您的程序未能在规定时间内运行结束，请检查是否循环有错或算法复杂度过大。

于是我们需要想到其他的方式，如何快速计算 3 的 n 次方，这是我们需要解决的问题，因为在尽量凑 3 的前提下，有以下三种情况：

被 3 整除等于 n ：直接计算 3 的 n 次幂
被 3 取余数为1，结果等于 n ：直接计算 3 的（n-1）次幂，再乘以4，为什么呢？因为余数是1，我们避免有1，需要借出 3，和 1凑成为 4，4 分段之后的最大乘积也是 4（2 * 2）
被 3 取余数为 2，结果等于 n：直接计算 3 的 n 次幂，再乘以2

在计算幂次方的时候，为了避免溢出，在每次相乘的时候，都需要除以998244353,为了计算快，每次以自身相乘的方式计算，代码如下：

public class Solution83 {
    //计算a^n次方的结果
    long pow(long a, long n) {
        long ans = 1;
        while (n > 0) {
            if (n % 2 == 1) ans = (ans * a) % 998244353;
            a = (a * a) % 998244353;
            // 自身乘以自身，快速计算
            n /= 2;
        }
        return ans;
    }

    public long cutRope(long number) {
        if (number == 2) return 1;
        if (number == 3) return 2;

        if (number % 3 == 0) {
            return pow(3, number / 3);
        } else if (number % 3 == 1) {
            return 4 * pow(3, (number - 4) / 3) % 998244353;
        } else {
            return (2 * pow(3, (number - 2) / 3)) % 998244353;
        }
    }
}

C++ 代码如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param number long长整型 
     * @return long长整型
     */
    long long cutRope(long long number) {
        if (number == 2) return 1;
        if (number == 3) return 2;

        if (number % 3 == 0) {
            return pow(3, number / 3);
        } else if (number % 3 == 1) {
            return 4 * pow(3, (number - 4) / 3) % 998244353;
        } else {
            return (2 * pow(3, (number - 2) / 3)) % 998244353;
        }
    }
    
        //计算a^n次方的结果
    long long pow(long a, long n) {
        long long ans = 1;
        while (n > 0) {
            if (n % 2 == 1) ans = (ans * a) % 998244353;
            a = (a * a) % 998244353;
            // 自身乘以自身，快速计算
            n /= 2;
        }
        return ans;
    }
};