Python 剪绳子的多种思路实现(动态规划和贪心)
剑指Offer(Python多种思路实现):剪绳子
面试14题：
题目：剪绳子
题：给你一根长度为n的绳子，请把绳子剪成m段(m,n都是整数，且n>1,m>1),每段绳子的长度记为k[0],k[1],k[2],...,k[m]。请问k[0]*k[1]*...*k[m]可能的最大乘积是多少？例如，当绳子的长度为8时，我们把它剪成长度分别为2，3，3的三段，此时得到的最大乘积为18。
解题思路一：基于动态规划和贪婪算法。
classSolution: defMaxProductAfterCut(self,n): #动态规划 ifn<2: return0 ifn==2: return1 ifn==3: return2 products=[0]*(n+1) products[0]=0 products[1]=1 products[2]=2 products[3]=3 foriinrange(4,n+1): max=0 forjinrange(1,i//2+1): product=products[j]*products[i-j] ifproduct>max: max=product products[i]=max #print(products) returnproducts[n] defMaxProductAfterCut2(self,n): #贪婪算法 ifn<2: return0 ifn==2: return1 ifn==3: return2 timesOf3=n//3 ifn-timesOf3*3==1: timesOf3-=1 timesOf2=(n-timesOf3*3)//2 return(3**timesOf3)*(2**timesOf2) if__name__=="__main__": print(Solution().MaxProductAfterCut(8)) print(Solution().MaxProductAfterCut(10)) #print(Solution().NumberOf1(0)) print(Solution().MaxProductAfterCut2(8)) print(Solution().MaxProductAfterCut2(10))
解题思路二：基于动态规划和贪婪算法。
classSolution: #动态规划 defmaxCut(self,n): ifn<2:return0 ifn==2:return1 ifn==3:return2 res=[0]*(n+1) res[0],res[1],res[2],res[3]=0,1,2,3 foriinrange(4,n+1): max=0 forjinrange(1,i//2+1): temp=res[j]*res[i-j] iftemp>max: max=temp res[i]=max#由下而上 returnres[n] #贪婪算法 defcutRope(length): iflength<2:return0 iflength==2:return1 iflength==3:return2 timesOf3=length//3#尽可能剪出3 iflength-timesOf3*3==1:#如果最后余1，则留一段4分成两半 timesOf3-=1 timesOf2=(length-timesOf3*3)//2 return(3**timesOf3)*(2**timesOf2)
到此这篇关于Python剪绳子的多种思路实现(动态规划和贪心)的文章就介绍到这了,更多相关Python剪绳子内容请搜索毛票票以前的文章或继续浏览下面的相关文章希望大家以后多多支持毛票票！
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。