Python 剪绳子的多种思路实现(动态规划和贪心)
作者:雾行 发布时间:2021-07-03 18:43:41
标签: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。
解题思路一:基于动态规划和贪婪算法。
class Solution:
def MaxProductAfterCut(self, n):
# 动态规划
if n<2:
return 0
if n==2:
return 1
if n==3:
return 2
products=[0]*(n+1)
products[0]=0
products[1]=1
products[2]=2
products[3]=3
for i in range(4,n+1):
max=0
for j in range(1,i//2+1):
product=products[j]*products[i-j]
if product>max:
max=product
products[i]=max
#print(products)
return products[n]
def MaxProductAfterCut2(self, n):
# 贪婪算法
if n < 2:
return 0
if n==2:
return 1
if n==3:
return 2
timesOf3 = n//3
if n - 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))
解题思路二:基于动态规划和贪婪算法。
class Solution:
# 动态规划
def maxCut(self, n):
if n<2: return 0
if n==2: return 1
if n==3: return 2
res=[0]*(n+1)
res[0], res[1], res[2], res[3]=0, 1, 2, 3
for i in range(4, n+1):
max = 0
for j in range(1, i//2+1):
temp = res[j]*res[i-j]
if temp>max:
max = temp
res[i]=max # 由下而上
return res[n]
# 贪婪算法
def cutRope(length):
if length<2: return 0
if length==2: return 1
if length==3: return 2
timesOf3 = length // 3 # 尽可能剪出3
if length-timesOf3*3 == 1: # 如果最后余1,则留一段4分成两半
timesOf3 -= 1
timesOf2 = (length-timesOf3*3) // 2
return (3**timesOf3) * (2**timesOf2)
来源:https://blog.csdn.net/weixin_44151089/article/details/104437866
0
投稿
猜你喜欢
- 可能出现的原因有:◆源数据库或目标数据库为 SQL Server 6.5 版。连接到 Access 项目的当前 SQL 服务器和要将数据库转
- 在Web开发中,JavaScript的一个很重要的作用就是对DOM进行操作,可你知道么?对DOM的操作是非常昂贵的,因为这会导致浏览器执行回
- 本文实例为大家分享了PHP变量传值赋值和引用赋值变量销毁的具体代码,供大家参考,具体内容如下<?php $a = 100
- 目的我们的目标是安装一个允许我们托管多个网站的web服务器,其中一些是针对电子商务的安全解决方案,而大部分网站是通过连接一个数据库服务器并且
- 首先要解释一下:“极致之美”不是说月儿的这篇文章,因为本人还没有自大到这种程度:P,它形容的是Lisp和javascript结合的优美形态。
- ndarray.ndim:维度ndarray.shape:形状ndarray.size:元素个数ndarray.dtype:元素数据类型nd
- 前言Windows10 在 UWP 应用中支持亚克力画刷,可以在部件的底部绘制亚克力效果的背景图。下面我们使用 QLabel 来模拟这个磨砂
- 作业备份,不是备份数据库,是备份作业。 我的方法是把作业导出成文件备份起来,因为当你服务器维护的多了的时候很多你的作业 就很成问题,很麻烦。
- 前言最近又多了不少朋友关注,先在这里谢谢大家。关注我的朋友大多数都是大学生,而且我简单看了一下,低年级的大学生居多,大多数都是为了完成课程设
- 本文实例为大家分享了Python实现图像增强的具体代码,供大家参考,具体内容如下题目描述:对于下面这幅图像(图 1),请问可以通过那些图像增
- 本文实例讲述了Python面向对象类的继承。分享给大家供大家参考,具体如下:一、概述面向对象编程 (OOP) 语言的一个主要功能就是“继承”
- 废话不多说了,直接给大家贴代码了,具体代码如下所示:// ----ajax begin $.ajax({type: "
- 目录执行原生 SQL 查询1、执行原生查询1.1 普通查询1.2 将查询字段映射为模型字段1.3 索引查询1.4 将参数传给 raw()2、
- 科讯5.0 标签和之前版本变化不大,如果用老版本的科讯,可以参考这个标签使用。相关文章:新云4.0 模板通用标签说明 标签清单:======
- 方法一:简单,得不到参数,只有一个虚拟路径 代码如下:GetUrl =request("url") 例如:http://
- 一、插入排序插入排序与我们平时打扑克牌非常相似,将新摸到的牌插入到已有的牌中合适的位置,而已有的牌往往是有序的。1.1 执行流程(1)在执行
- 如下所示:var myarr=new Array(); //先声明一维 for(var i=0;i<2;i++){ //一
- 1、字符串的索引与获取字符串的索引方式与列表的索引方式是一样的。只不过列表是每个元素的自身就有一个索引位置,而字符串是每个字符就有一个索引位
- 以下排序算法最终结果都默认为升序排列,实现简单,没有考虑特殊情况,实现仅表达了算法的基本思想。冒泡排序内层循环中相邻的元素被依次比较,内层循
- 开源的MySQL并不能取代非共享的私有数据库在企业中的应用,于是这些开源数据库的支持者们想把解决Web应用程序开发工具的可扩展性问题看作是获