关于java:offer-14I-减绳子

减绳子

看到题目首先感觉是递归算法-动静布局 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，因为22>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])。
• 其实就是定义来源gaodai#ma#com搞*代#码网绳子失去的最大乘积状态：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。
• 当作为后果返回时，必须要切一段，不能不切。然而如果不是递归调用就能够不必切

喜欢 (0)赏

[搞代码]

分享 (0)