14. 剪绳子
剪绳子
http://www.nowcoder.com/questionTerminal/57d85990ba5b440ab888fc72b0751bf8
- 利用动态规划，需要O(n^2)时间和O(n)空间，也就是利用一个表，储存长度为1~n绳子的最大乘积。
class Solution:
def cutRope(self, number):
# write code here
if number < 2: return 0
if number == 2:return 1
if number == 3:return 2
products = [0, 1, 2, 3]
for i in range(4, number+1, 1):
product = 0
for j in range(1,4//2+1,1):
res = products[j]* products[i-j]
product = max(res,product)
products.append(product)
return products[-1]- 贪婪算法：这种想法比较巧妙，尽量把大于5的数分解成3的乘积，如果剩下的长度为4，则把4分解成2和2，因为3
1 < 2
class Solution:
def cutRope(self, number):
# write code here
if number < 2: return 0
if number == 2:return 1
if number == 3:return 2
timesof3 = number // 3
if number - timesof3 * 3 == 1:
timesof3 -= 1
timesof2 = (number - timesof3 * 3) / 2
return (3**timesof3)*(2**timesof2)
