AcWing 25. 剪绳子
原题链接
简单
作者:
buchiyu
,
2021-05-11 10:28:24
,
所有人可见
,
阅读 192
贪心
class Solution(object):
def maxProductAfterCutting(self,length):
"""
:type length: int
:rtype: int
"""
if length <= 2: return 1 * (length - 1)
rest = length % 3
if rest == 0:
return 3**(length //3)
elif rest == 1:
return 3**(length // 3 - 1)*4
else:
return 3**(length // 3) * 2
动态规划
class Solution(object):
def maxProductAfterCutting(self,length):
if length <= 2: return 1 * (length - 1)
dp = [0 for i in range(length + 1)]
for i in range(2,length + 1):
for j in range(2, i):
tmp = max(j* (i - j), j*dp[i - j])
dp[i] = max(dp[i], tmp)
return dp[length]