文章目录

1. 题目2. 解题思路3. 代码实现3.1 动态规划3.2 贪心算法 4. 总结5. 参考文献

1. 题目

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

2. 解题思路

详情 leetcode 面试题14- I. 剪绳子（数学推导 / 贪心思想，清晰图解）

3. 代码实现

3.1 动态规划

class Solution: def cuttingRope(self, n: int) -> int: """ 动态规划 f(n) = max(f(i) * f(n-i)) """ # 初始化 if n < 2: return 0 if n == 2: return 1 if n == 3: return 2 records = list(range(n+1)) max_ = 0 for i in range(4, n+1): max_ = 0 # 比较出最大值 for j in range(1, i//2 + 1): temp = records[j] * records[i-j] if max_ < temp: max_ = temp records[i] = max_ return records[n]

3.2 贪心算法

import math class Solution: def cuttingRope(self, n: int) -> int: if n < 2: return 0 if n == 2: return 1 if n == 3: return 2 # 尽可能多地剪去长度为3的绳子长度 times_of_3 = n // 3 # 当绳子最后剩下的长度为4的时候，不能再剪去长度为3的绳子段 # 此时更好的方法是把绳子剪成长度为2的两段，因为2*2 > 3*1 if n - times_of_3 * 3 == 1: times_of_3 -= 1 times_of_2 = (n - times_of_3 * 3)//2 return int(math.pow(3, times_of_3) * math.pow(2, times_of_2))

4. 总结

动态规划和贪婪有些复杂。。。

5. 参考文献

[1] 剑指offer丛书 [2] 剑指Offer——名企面试官精讲典型编程题