题解 | #剪绳子#

剪绳子

http://www.nowcoder.com/practice/57d85990ba5b440ab888fc72b0751bf8

这是个数学问题,存在这样一个“定律”:
考虑一个比较大的数字n,当他被减掉m的时候:
如果n-m >= n/2,且m >= 2,显然(n-m)*m要比原值n更大

那么当m = 1时,没有意义
m等于2时,增幅2倍
m等于3时,增幅3倍,效果比m=2时更强
当m等4时,m本身也开始使用“定律”,因此4本身也可切分为2和2,只是这种切分和原值恰好一致
当m等5时,必然需要切分,切分后转化为2、3, 23>5
因此,切分的值m不必大于3,而切分为2还是切分为3,由举例规律我们可以直接知道,例如6:
6 = 2 + 2 + 2, 2
22 = 8
6 = 3 + 3, 3
3 = 9
显然,应当先切分出3即可

应用数学原理则完全不必考虑动态规划问题

# -*- coding:utf-8 -*-
class Solution:
    def cutRope(self, number):
        result = 1
        while number > 4:
            result *= 3
            number -= 3
        result *= number
        return result

        # write code here
全部评论
符号乘被隐藏了
点赞 回复 分享
发布于 2021-08-19 18:13

相关推荐

lllllkin:感觉可以精简到一页简历,有些排版感觉不是必须的。 时间线越早的,你自己越熟悉的放前面。描述可以更精简些,一些问题解决感觉可以不用写具体技术栈,卖个关子,等面试官问。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务