14. 剪绳子

题目链接

Leetcode

题目描述

把一根长度为 n 的绳子剪成多段（至少剪一刀，n ≥ 2），每段长度为整数，求各段长度乘积的最大值。

n = 2
return 1 (2 = 1 + 1)

n = 10
return 36 (10 = 3 + 3 + 4)

解题思路

贪心

结论：尽可能多剪长度为 3 的段；剩下 1 时，把一个 3 + 1 改成 2 + 2；剩下 2 时，单独留一段 2。例如 n = 10 = 3 + 3 + 4，乘积 3 × 3 × 4 = 36。

推导分三步：

• 不会出现长度为 1 的段：把 1 并到相邻的一段 x 上，乘积从 x 变为 x + 1，更大；
• 不会出现长度不小于 5 的段：把它拆成 2 和 x - 2，2(x - 2) - x = x - 4 > 0，乘积更大。长度为 4 的段与 2 + 2 的乘积相同，可以看成两段 2，因此只剩下 2 和 3；
• 长度为 2 的段最多两段：三段 2 的总长与两段 3 相同，而 2 × 2 × 2 = 8 < 3 × 3 = 9。

所以 n 除以 3 余 0 时全是 3；余 1 时最后是 2 + 2；余 2 时最后是一个 2。n = 2、3 时必须至少剪一刀，答案分别是 1 和 2，要单独处理。

public int cuttingBamboo(int bamboo_len) {
    if (bamboo_len < 2)
        return 0;
    if (bamboo_len == 2)
        return 1;
    if (bamboo_len == 3)
        return 2;
    int timesOf3 = bamboo_len / 3;
    if (bamboo_len - timesOf3 * 3 == 1)
        timesOf3--;
    int timesOf2 = (bamboo_len - timesOf3 * 3) / 2;
    return (int) (Math.pow(3, timesOf3)) * (int) (Math.pow(2, timesOf2));
}

动态规划

dp[i] 表示长度为 i 的绳子剪过至少一刀后的最大乘积。枚举最后一段的长度 i - j，前面的 j 不再剪时乘积为 j × (i - j)，继续剪时为 dp[j] × (i - j)，取最大值。时间复杂度 O(N²)。

public int cuttingBamboo(int bamboo_len) {
    int[] dp = new int[bamboo_len + 1];
    dp[1] = 1;
    for (int i = 2; i <= bamboo_len; i++)
        for (int j = 1; j < i; j++)
            dp[i] = Math.max(dp[i], Math.max(j * (i - j), dp[j] * (i - j)));
    return dp[bamboo_len];
}