题解 | #剪绳子#
剪绳子
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, 222 = 8
6 = 3 + 3, 33 = 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