67 剪绳子

题目描述

给你一根长度为n的绳子，请把绳子剪成整数长度的m段（m、n都是整数，n>1并且m>1），每段绳子的长度记为k[0],k[1],...,k[m]。请问k[0]xk[1]x...xk[m]可能的最大乘积是多少？

解题思路

方法一：动态规划

核心思想：dp[i]表示长度为i的绳子能得到的最大乘积。

方法二：数学方法

核心思想：尽可能多剪成长度为3的段。

时间复杂度：O(n)（DP）或 O(1)（数学） 空间复杂度：O(n)（DP）或 O(1)（数学）

Python 实现

# 方法一：动态规划
def max_product_cutting_dp(n):
    """
    剪绳子的最大乘积（动态规划）
    """
    if n <= 1:
        return 0
    if n == 2:
        return 1
    if n == 3:
        return 2

    dp = [0] * (n + 1)
    dp[1] = 1
    dp[2] = 2
    dp[3] = 3

    for i in range(4, n + 1):
        max_product = 0
        for j in range(1, i // 2 + 1):
            max_product = max(max_product, dp[j] * dp[i - j])
        dp[i] = max_product

    return dp[n]


# 方法二：数学方法
def max_product_cutting(n):
    """
    剪绳子的最大乘积（数学方法）
    """
    if n <= 1:
        return 0
    if n == 2:
        return 1
    if n == 3:
        return 2

    # 尽可能多剪3
    times_of_3 = n // 3

    # 如果余数为1，退一个3
    if n % 3 == 1:
        times_of_3 -= 1
        return 3 ** times_of_3 * 4
    # 如果余数为2
    elif n % 3 == 2:
        return 3 ** times_of_3 * 2

    return 3 ** times_of_3


# 测试代码
if __name__ == "__main__":
    test_cases = [2, 3, 4, 5, 10]

    for n in test_cases:
        print(f"长度{n}, 最大乘积: {max_product_cutting(n)}")

# 输出:
# 长度2, 最大乘积: 1
# 长度3, 最大乘积: 2
# 长度4, 最大乘积: 4
# 长度5, 最大乘积: 6
# 长度10, 最大乘积: 36

图解

数学方法分析:
- 当长度>=5时，剪出长度为3的段是最优的
  - 因为3x2 > 5, 3x3 > 2x4

余数处理:
- 余数为0: 全部剪成3
- 余数为1: 3x1 < 2x2，所以退一个3，剪成2x2
- 余数为2: 直接剪成3...x2

示例: n=10
10 = 3 + 3 + 3 + 1
余数为1，退一个3
10 = 3 + 3 + 2 + 2
乘积 = 3 x 3 x 2 x 2 = 36