算法:剪绳子之大数越界情况下的求余问题

算法:剪绳子之大数越界情况下的求余问题

首页休闲益智切绳子大作战更新时间:2024-04-26

贪心思想 快速幂求余

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

答案需要取模 1e9 7(1000000007),如计算初始结果为:1000000008,请返回 1。

示例1示例2提示方法:快速幂求余

设一绳子长度为 n ( n>1 ),则其必可被切分为两段 n=n1 n2

根据经验推测,切分的两数字乘积往往比原数字更大,即往往有 n1 × n2 >n1 n2 =n 。

推论一: 合理的切分方案可以带来更大的乘积

设一绳子长度为 n ( n>1),切分为两段 n=n1 n2,切分为三段 n=n1 n2 n3。

根据经验推测,三段 的乘积往往更大,即往往有 n1n2n3 >n1n2

推论二: 若切分方案合理,绳子段切分的越多,乘积越大

总体上看,貌似长绳子切分为越多段乘积越大,但其实到某个长度分界点后,乘积到达最大值,就不应再切分了。

问题转化: 是否有优先级最高的长度 x 存在?若有,则应该尽可能把绳子以 x 长度切为多段,以获取最大乘积。

推论三: 为使乘积最大,只有长度为 2 和 3 的绳子不应再切分,且 3 比 2 更优

详情见下表

代码如下:

复杂度分析END

本文内容出处是力扣官网,希望和大家一起刷算法,在后面的路上不变秃但是变强!

好兄弟可以点赞并关注我的公众号“javaAnswer”,全部都是干货。

查看全文
大家还看了
也许喜欢
更多游戏

Copyright © 2024 妖气游戏网 www.17u1u.com All Rights Reserved