Python 剪绳子的多种思路实现(动态规划和贪心)

2024-08-20 17:47:52

剑指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)

到此这篇关于Python 剪绳子的多种思路实现(动态规划和贪心)的文章就介绍到这了,更多相关Python 剪绳子内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

动态规划之矩阵连乘问题Python实现方法

本文实例讲述了动态规划之矩阵连乘问题Python实现方法.分享给大家供大家参考,具体如下: 给定n个矩阵{A1,A2,-,An},其中Ai与Ai+1是可乘的,i=1,2 ,-,n-1.如何确定计算矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最少. 例如: A1={30x35} ; A2={35x15} ;A3={15x5} ;A4={5x10} ;A5={10x20} ;A6={20x25} ; 结果为:((A1(A2A3))((A4A5)A6)) 最小的乘次为15125.
python实现最大子序和（分治+动态规划）

给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和. 示例: 输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大,为 6. 进阶: 如果你已经实现复杂度为 O(n) 的解法,尝试使用更为精妙的分治法求解. 思路: 首先我们分析题目,我们思考,为什么最大和的连续子数组不包含其他的元素而是这几个呢?因为如果我们想在现有的基础上去扩展当前连续子数组,相邻的元素是一定要被加入的,而相邻
python实现对求解最长回文子串的动态规划算法

基于Python实现对求解最长回文子串的动态规划算法,具体内容如下 1.题目给定一个字符串 s,找到 s 中最长的回文子串.你可以假设 s 的最大长度为1000. 示例 1: 输入: "babad" 输出: "bab" 注意: "aba"也是一个有效答案. 示例 2: 输入: "cbbd" 输出: "bb" 2.求解对于暴力求解在这里就不再骜述了,着重介绍如何利用动态规划算法进行求解. 关于动态规划的含
Python基于动态规划算法解决01背包问题实例

本文实例讲述了Python基于动态规划算法解决01背包问题.分享给大家供大家参考,具体如下: 在01背包问题中,在选择是否要把一个物品加到背包中,必须把该物品加进去的子问题的解与不取该物品的子问题的解进行比较,这种方式形成的问题导致了许多重叠子问题,使用动态规划来解决.n=5是物品的数量,c=10是书包能承受的重量,w=[2,2,6,5,4]是每个物品的重量,v=[6,3,5,4,6]是每个物品的价值,先把递归的定义写出来: 然后自底向上实现,代码如下: def bag(n,c,w,v): re
分析python动态规划的递归、非递归实现

概要本文只是简单的介绍动态规划递归.非递归算法实现案例一题目一:求数组非相邻最大和 [题目描述] 在一个数组arr中,找出一组不相邻的数字,使得最后的和最大. [示例输入] arr=1 2 4 1 7 8 3 [示例输出] 15 from functools import wraps def memoDeco(func): ''' memoDeco主要是缓存已遍历的节点,减少递归内存开销 ''' cashe={} @wraps(func) def wrapper(*args): if ar
Python基于动态规划算法计算单词距离

本文实例讲述了Python基于动态规划算法计算单词距离.分享给大家供大家参考.具体如下: #!/usr/bin/env python #coding=utf-8 def word_distance(m,n): """compute the least steps number to convert m to n by insert , delete , replace . 动态规划算法,计算单词距离 >>> print word_distance("
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
Python对称的二叉树多种思路实现方法

对称二叉树的含义非常容易理解,左右子树关于根节点对称,具体来讲,对于一颗对称二叉树的每一颗子树,以穿过根节点的直线为对称轴,左边子树的左节点=右边子树的右节点,左边子树的右节点=左边子树的左节点.所以对称二叉树的定义是针对一棵树,而判断的操作是针对节点,这时可以采取由上到下的顺序,从根节点依次向下判断,只需要重复调用函数,不需要回溯. 题目:对称的二叉树题: 请实现一个函数,用来判断一颗二叉树是不是对称的.注意,如果一个二叉树同此二叉树的镜像是同样的,定义其为对称的解题思路一:先遍历右子节点再
Python 字符串换行的多种方式

第一种: x0 = '<?xml version="1.0"?>' \ '<ol>' \ ' <li><a href="/python" rel="external nofollow" rel="external nofollow" rel="external nofollow" rel="external nofollow" >Pytho
python实现爬山算法的思路详解

问题找图中函数在区间[5,8]的最大值重点思路爬山算法会收敛到局部最优,解决办法是初始值在定义域上随机取乱数100次,总不可能100次都那么倒霉. 实现 import numpy as np import matplotlib.pyplot as plt import math # 搜索步长 DELTA = 0.01 # 定义域x从5到8闭区间 BOUND = [5,8] # 随机取乱数100次 GENERATION = 100 def F(x): return math.sin(x*x)
Python中断多重循环的思路总结

I. 跳出单循环不管是什么编程语言,都有可能会有跳出循环的需求,比如枚举时,找到一个满足条件的数就终止.跳出单循环是很简单的,比如: for i in range(10): if i > 5: print i break 然而,我们有时候会需要跳出多重循环,而break只能够跳出一层循环,比如: for i in range(10): for j in range(10): if i+j > 5: print i,j break 这样的代码并非说找到一组 i+j > 5就停止,而是连续
Python模拟登录的多种方法(四种)

正文方法一:直接使用已知的cookie访问特点: 简单,但需要先在浏览器登录原理: 简单地说,cookie保存在发起请求的客户端中,服务器利用cookie来区分不同的客户端.因为http是一种无状态的连接,当服务器一下子收到好几个请求时,是无法判断出哪些请求是同一个客户端发起的.而"访问登录后才能看到的页面"这一行为,恰恰需要客户端向服务器证明:"我是刚才登录过的那个客户端".于是就需要cookie来标识客户端的身份,以存储它的信息(如登录状态). 当然,这也
python实现括号匹配的思路详解

1.用一个栈[python中可以用List]就可以解决,时间和空间复杂度都是O(n) # -*- coding: utf8 -*- # 符号表 SYMBOLS = {'}': '{', ']': '[', ')': '(', '>': '<'} SYMBOLS_L, SYMBOLS_R = SYMBOLS.values(), SYMBOLS.keys() def check(s): arr = [] for c in s: if c in SYMBOLS_L: # 左符号入栈 arr.appe
python的concat等多种用法详解

本文为大家分享了python的concat等多种用法,供大家参考,具体内容如下 1.numpy中的concatenate()函数: >>> a = np.array([[1, 2], [3, 4]]) >>> b = np.array([[5, 6]]) >>> np.concatenate((a, b), axis=0) array([[1, 2], [3, 4], [5, 6]]) >>> np.concatenate((a, b
python循环嵌套的多种使用方法解析

这篇文章主要介绍了python循环嵌套的多种使用方法解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下使用循环嵌套来获取100以内的质数 #!/usr/bin/python # -*- coding: UTF-8 -*- num=[]; i=2 for i in range(2,100): j=2 for j in range(2,i): if(i%j==0): break else: num.append(i) print(num) 使用嵌
python 读写文件包含多种编码格式的解决方式

今天写一个脚本文件,需要将多个文件中的内容汇总到一个txt文件中,由于多个文件有三种不同的编码方式,读写出现错误,先将解决方法记录如下: # -*- coding: utf-8 -*- import wave import pylab as pl import numpy as np import pandas as pd import os import time import datetime import arrow import chardet import sys reload(sys

Python 剪绳子的多种思路实现(动态规划和贪心)

相关推荐

随机推荐