（python）剑指Offer（第二版）面试题14：剪绳子
发布于2019-08-03 08:52 阅读(5938) 评论(0) 点赞(6) 收藏(0)
题目
给你一根长度为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.
解题思想
动态规划（具体解法及思路见代码注释）
解题代码（python实现）
# 题目一：给你一根长度为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. #解题思路：动态规划 def rope_cut(length): # 最优解数组，当长度为0是为0，当长度为1是为1，当长度为2时为2，当长度大于3时，3就不能切开了，因为3>1*2，最优解数组为3 li=[0,1,2,3] if length==0:#当长度为0时，返回0 return 0 if length==1:#当长度为1时，返回1 return 1 if length==2:#当长度为2时，返回2 return 2 if length==3:#当长度为3时，返回2，虽然最优解数组里为2，但是每次必须得切一刀，这样1*2=2，所以长度为3时还是2 return 2 for j in range(4,length+1): max = 0 for i in range(1,j): # 思路：每次求解值时将其他小于需要求解的长度是都列出来放在一个数组里 #如：求长度为5，最优解数组里必须得有长度为1,2,3,4的最优解值 #注：此处使用列表保存最优解数组是为了性能优化，虽然递归求解也能解出，但会造成大量重复执行 temp=li[i]*li[j-i] if temp>max: max=temp li.append(max)#每次将上次所得最优解追加在列表里 return li[-1] print(rope_cut(8))
（ps：只想说，解出一道题的感觉真的好爽）
所属网站分类: 技术文章 > 博客
作者：听爸爸的话
链接：https://www.pythonheidong.com/blog/article/3809/fb0d56cf9c569793d8d5/
来源：python黑洞网
任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任
昵称:
评论内容：(最多支持255个字符)
---无人问津也好，技不如人也罢，你都要试着安静下来，去做自己该做的事，而不是让内心的烦躁、焦虑，坏掉你本来就不多的热情和定力