共计 1128 个字符，预计需要花费 3 分钟才能阅读完成。
减绳子
看到题目首先感觉是递归算法 - 动静布局 Dynamic Programming– 从菜鸟到老鸟
题目剖析
本题目就是剖析 k0k1……*km 的最大值
依据数学公式
简略来说就是须要比拟 axb 和 ((a+b)/2) x ((a+b)/2) 的大小，a* b 的最大值就是 ((a+b)/2) x ((a+b)/2)，当且仅当 a = b 时成立，所以原题目就是 当外面的 n1 n2 na 全副相等式等号成立 ，也就是均分
依照题目通过计算找到极值点发现是 e，然而题目要求必须为整数，也就是 2 或者 3，而后通过计算发现整数取 3 的时候能够失去最大值，乘积最大。
切分规定 找法则
- 把绳子尽可能的切成多个长度时 3 的，最初留下的最初一段绳子应该长度时 0 1 2
- 如果最初一段的绳子长度是 2，就不剪了，因为 2 >1*1
- 如果最初一段的绳子长度是 1，就应该把倒数第二段的 3 合起来，变成 4 而后拆成 2 +2，因为 2 2>13，此时后面都是全副是 3 的绳子段子，只是最初两段变了
题解
牛批写法：和三为一：return n <= 3? n - 1 : pow(3, n / 3) * 4 / (4 - n % 3);这个合三为 1 真的是很强了
这个是以 4 为临界点，因为 4 除 3 余 1，所以遇到最初宰割剩下 4 就跳出循环而后间接×剩下的 4，如果不是 4，是 5，那就剩下 2，持续运算就好了
递归算法 没找到法则的话
- 基本思路：采纳动静布局办法。定义 dp 状态 result[i]为绳长为 i 时，绳子的可能最大长度乘积。上面咱们探索递推关系，对于绳长为 i 的绳子，咱们抉择在 j 地位将绳子剪断，此时绳子被分成长度为 j 和长度为 i – j 的两局部，此时剪断之后绳子可能的最大长度乘积，为绳长为 j 和绳长 i – j 时候后果的积。而 dp 状态更新为 max(result[i],result[j] × result[i – j])。
- 其实就是定义绳子失去的最大乘积状态：dp 状态 result[i]为绳长为 i 时，绳子的可能最大长度乘积
- 而后将 i 此时失去的最大乘积值存到数组里，而后将 i 持续裁剪又能够将 i 的绳子分为 j 和 i -j，那么此时绳子的最大乘积为 j *（i-j）, 也就是此时 dp 状态 result[i]的最大乘积应该是 max(result[i],result[j] × result[i – j])，万一剪开之后乘积不如原来的大呢，所以就得利用 max 找到最大的
- dp 数组的长度：因为定义 result[i]为绳长度为 i 时的后果，因而 result[n]为最初一项，所以数组的总长度为 n + 1
- j 的遍历范畴：如果 j > i/2，那么 result[j]曾经由之前的 result[i – j]遍历过，导致反复计算，因而 j 最多遍历到 i /2。同时，因为题目规定必须要切一刀，因而不能使得某一段的长度为 0，因而 j 起码遍历到 1。
- 当作为后果返回时，必须要切一段，不能不切。然而如果不是递归调用就能够不必切
正文完