题目：给你一根长度为n的绳子，请把绳子剪成m段 (m和n都是整数，n>1并且m>1)每段绳子的长度记为k[0],k[1],…,k[m].请问k[0]k[1]…*k[m]可能的最大乘积是多少？例如，当绳子的长度为8时，我们把它剪成长度分别为2,3,3的三段，此时得到的最大乘积是18.
解题思路：动态规划
#面试题14：剪绳子
class Solution:
def dynamic_programming(self, n):
if n < 2: #长度<2，为0
return 0
if n == 2: #长度=2，剪成两段1
return 1
if n == 3: #长度=3,1x2
return 2
tmp_lst = [0, 1, 2, 3]
for i in range(4, n+1): #长度>4
max = 0
for j in range(1, i): #从下往上分析问题
tmp = tmp_lst[j] * tmp_lst[i - j]
if max < tmp:
max = tmp
tmp_lst.append(max)
return tmp_lst[n]
s = Solution()
print(s.dynamic_programming(8))竟然大概看懂（人家的代码）了……安不里屋包
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
