剑指 Offer 14- I & II: 剪绳子

[songyy5517]

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

示例 1：

输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1

示例 2:

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36

分析 这道题需要我们求长度n绳子分段的最大乘积。一个很直接的想法是，对与长度为n的绳子，我们可以固定其中的长度i，因此其最大乘积是所有 i 乘(n - i)长度绳子中的最大乘积。因此我们可以使用动态规划，可将长度为i绳子的最大乘积看作是一个状态f[i]，初始状态下的长度为1，2，3，最终返回状态f[n]即可。

[songyy5517]

思路1：动态规划

1. 异常处理（n = 1, 2, 3）；
2. 定义状态：f[i] 表示长度为i的绳子的最大乘积；
3. 状态初始化：f[1] = 1, f[2] = 2, f[3] = 3；
4. 自下而上计算各个状态；
   • 对每个状态f[i]，固定长度j，其中j∈[1, i/2]；
   • f[i] 为所有 f[j] * f[i - j] 的最大值。
5. 返回最终状态 f[n]。

复杂度分析

• 时间复杂度： $O(N^2)$ ，计算各个状态的过程使用了双层循环，复杂度为 $O(N^2)$ ；
• 空间复杂度： $O(N)$ ，额外定义了 $O(N)$ 大小的数组存放各个状态。

[songyy5517]

import java.util.*;

public class Solution {
    public int cutRope (int n) {
        // write code here
        // 思路：DP

        // 1. 异常处理
        if (n <= 2)
            return 1;
        if (n == 3)
            return 2;

        int[] f = new int[n + 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] = Math.max(f[i], f[j] * f[i - j]);
        }

        return f[n];
    }
}

[songyy5517]

思路2：贪心算法

1. 异常处理（n <= 3）；
2. 定义并初始化变量max_sum = 1记录最大乘积；
3. 当n > 3时执行以下循环： （1）max_sum *= 3; （2）n -= 3；
4. 跳出循环时，当n = 1时，返回 max_sum / 3 4，否则返回 max_sum 3。

为什么要以3为基准？ 由均值不等式 $(x_1 + x_2 + ... + x_n) / i \ge \sqrt[i]{x_1 ... x_n}$ 可推出当 $x_1 = x_2 = ... = x_n$ 时，即每段长度相等， $x_1...x_n$ 有最大值。设每段长度为 $x$ ，则乘积为 $x^m = x^{n/x} = (x^{1/x})^n$ 。根据一系列数学取对数求导求极值操作，可得驻点 $x = e$ ，而 $x$ 必须要为整数，因此 $x = 3$ 。

复杂度分析

• 时间复杂度： $O(N)$ ，一共进行 $n / 3$ 次循环，使用了 $O(N)$ 大小的时间；
• 空间复杂度： $O(1)$ ，额外定义了常数大小的变量。

[songyy5517]

2023/1/20

• 初始化f[0:3]时，直接赋值长度就行了

2024/4/2