14. 剪绳子

文档摘要

剪绳子题目链接牛客网题目描述把一根绳子剪成多段，并且使得每段的长度乘积最大。解题思路贪心尽可能得多剪长度为 3 的绳子，并且不允许有长度为 1 的绳子出现。如果出现了，就从已经切好长度为 3 的绳子中拿出一段与长度为 1 的绳子重新组合，把它们切成两段长度为 2 的绳子。以下为证明过程。将绳子拆成 1 和 n-1，则 1(n-1)-n=-1\ =4 时这样拆开能得到的乘积会比不拆更大。将绳子拆成 3 和 n-3，则 3(n-3)-n = 2n-9，在 n\>=5 时效果更好。将绳子拆成 4 和 n-4，因为 4=2\2，因此效果和拆成 2 一样。将绳子拆成 5 和 n-5，因为 5=2+3，而 5\ = 0，在 n\>=5 的情况下将绳子拆成 3 比拆成 2 效果更好。