【Python刷题Leetcode】动态规划(爬楼梯/打家劫舍/最大字段和/找零钱/三角形/最长上升子序列/最小路径和/地牢游戏)

本文主要是介绍【Python刷题Leetcode】动态规划(爬楼梯/打家劫舍/最大字段和/找零钱/三角形/最长上升子序列/最小路径和/地牢游戏),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

class Solution:# 递归法 超时了def climbStairs1(self, n: int) -> int:if n==1 or n==2:return n# 第1次爬1阶 共climbStairs1(n-1);第1次爬2阶 共climbStairs1(n-2);return self.climbStairs1(n-1)+self.climbStairs1(n-2)# 动态规划(dp)def climbStairs(self, n: int) -> int:dp = [0]*(n+3) # 最短是3个值 防止后面for循环越界dp[0],dp[1],dp[2]=0,1,2for i in range(3,n+1):dp[i]=dp[i-1]+dp[i-2]return dp[n]

 

class Solution:def rob(self, nums: List[int]) -> int:if len(nums)==0:return 0if len(nums)==1:return nums[0]if len(nums)==2:return max(nums[0],nums[1])# len(nums) >=3dp = [0]*(len(nums))dp[0],dp[1]=nums[0],max(nums[0],nums[1])for i in range(2,len(nums)):dp[i]=max(dp[i-1], dp[i-2]+nums[i])return dp[-1]

 

class Solution:def maxSubArray(self, nums: List[int]) -> int:dp = [0]*len(nums)dp[0] = nums[0]max_res = dp[0]for i in range(1, len(nums)):# 以nums[i]为结尾的结果dp[i]=max(dp[i-1]+nums[i], nums[i])if dp[i]>max_res:max_res = dp[i]return max_res

 

class Solution:def coinChange(self, coins: List[int], amount: int) -> int:# dp[i]是指的组成金额i所需的最少硬币数dp = [-1]*(amount+1)dp[0] = 0# 动态规划 从dp[1]开始递推for i in range(1,amount+1):# 内层循环coinsfor coin in coins:# 若i包含面值coin且i去掉coin后可达if i-coin>=0 and dp[i-coin]!=-1:# dp[i] = min(dp[i-1],dp[i-2],dp[i-5]) + 1 其中1 2 5是面值if dp[i]==-1 or dp[i-coin]+1<dp[i]:dp[i]=dp[i-coin]+1return dp[amount]

 

 

class Solution:def minimumTotal(self, triangle: List[List[int]]) -> int:if not triangle:return 0# triangle就是dp 最后一行不变 从倒数第二行往上递推for i in range(1,len(triangle)):line = len(triangle)-1-ifor j in range(len(triangle[line])):triangle[line][j]+=min(triangle[line+1][j],triangle[line+1][j+1])return triangle[0][0]

class Solution:def lengthOfLIS(self, nums: List[int]) -> int:if len(nums)==0 or len(nums)==1:return len(nums)# dp[i]表示nums[i]为结尾的最长上升子序列长度 # dp[i+1] = max(dp[0],dp[1],..,dp[i])+1 其中max()里面对应的num都小于nums[i+1]dp = [1]*len(nums)res = 1for i in range(1, len(nums)):for j in range(0,i):if nums[i]>nums[j] and dp[j]+1>dp[i]:dp[i]=dp[j]+1if dp[i]>res:res=dp[i]return res

另一个算法:

class Solution:def minPathSum(self, grid: List[List[int]]) -> int:if not grid:return 0# 获取行和列m = len(grid)n = len(grid[0])# 初始化dp为全0 形状跟grid一样dp = []for i in range(m):tmp = []for j in range(n):tmp.append(0)dp.append(tmp)# 从左上到右下动态规划dp[0][0] = grid[0][0]# 初始化第0行for i in range(1,n):dp[0][i] = grid[0][i]+dp[0][i-1] # grid[0][i]只能从左边过来# 从第1行开始遍历for i in range(1,m):# 初始化第i行第0列dp[i][0] = grid[i][0]+dp[i-1][0]# 填其他列 要么从左边过来 要么从上边过来for j in range(1,n):dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j]return dp[m-1][n-1]

 

class Solution:def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:if not dungeon:return 0# 获取行和列m = len(dungeon)n = len(dungeon[0])# 初始化dp为全0 形状跟dungeon一样dp = []for i in range(m):tmp = []for j in range(n):tmp.append(0)dp.append(tmp)# 初始化最后一个元素dp[m-1][n-1] = max(1, 1-dungeon[m-1][n-1])# 初始化最后一行0 ~ n-2 个元素for i in range(0,n-1):idx = n-2-idp[m-1][idx] = max(1, dp[m-1][idx+1]-dungeon[m-1][idx])# 初始化最后一列0 ~ m-2 个元素for i in range(0,m-1):idx = m-2-idp[idx][n-1] = max(1, dp[idx+1][n-1]-dungeon[idx][n-1])# print(dp)# 从倒数第2行开始往上遍历 遍历m-2 ~ 0 行, 每行遍历前n-2 ~ 0 列for i in range(0,m-1):row = m-2-ifor j in range(0,n-1):col = n-2-jprint(row,col)dp_min = min(dp[row+1][col],dp[row][col+1]) # 正下方 or 正右方dp[row][col]=max(1, dp_min-dungeon[row][col])# print(dp)return dp[0][0]

 

这篇关于【Python刷题Leetcode】动态规划(爬楼梯/打家劫舍/最大字段和/找零钱/三角形/最长上升子序列/最小路径和/地牢游戏)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/520764

相关文章

Python进行JSON和Excel文件转换处理指南

《Python进行JSON和Excel文件转换处理指南》在数据交换与系统集成中,JSON与Excel是两种极为常见的数据格式,本文将介绍如何使用Python实现将JSON转换为格式化的Excel文件,... 目录将 jsON 导入为格式化 Excel将 Excel 导出为结构化 JSON处理嵌套 JSON:

Python操作PDF文档的主流库使用指南

《Python操作PDF文档的主流库使用指南》PDF因其跨平台、格式固定的特性成为文档交换的标准,然而,由于其复杂的内部结构,程序化操作PDF一直是个挑战,本文主要为大家整理了Python操作PD... 目录一、 基础操作1.PyPDF2 (及其继任者 pypdf)2.PyMuPDF / fitz3.Fre

python设置环境变量路径实现过程

《python设置环境变量路径实现过程》本文介绍设置Python路径的多种方法:临时设置(Windows用`set`,Linux/macOS用`export`)、永久设置(系统属性或shell配置文件... 目录设置python路径的方法临时设置环境变量(适用于当前会话)永久设置环境变量(Windows系统

python中列表应用和扩展性实用详解

《python中列表应用和扩展性实用详解》文章介绍了Python列表的核心特性:有序数据集合,用[]定义,元素类型可不同,支持迭代、循环、切片,可执行增删改查、排序、推导式及嵌套操作,是常用的数据处理... 目录1、列表定义2、格式3、列表是可迭代对象4、列表的常见操作总结1、列表定义是处理一组有序项目的

python运用requests模拟浏览器发送请求过程

《python运用requests模拟浏览器发送请求过程》模拟浏览器请求可选用requests处理静态内容,selenium应对动态页面,playwright支持高级自动化,设置代理和超时参数,根据需... 目录使用requests库模拟浏览器请求使用selenium自动化浏览器操作使用playwright

python使用try函数详解

《python使用try函数详解》Pythontry语句用于异常处理,支持捕获特定/多种异常、else/final子句确保资源释放,结合with语句自动清理,可自定义异常及嵌套结构,灵活应对错误场景... 目录try 函数的基本语法捕获特定异常捕获多个异常使用 else 子句使用 finally 子句捕获所

Python极速搭建局域网文件共享服务器完整指南

《Python极速搭建局域网文件共享服务器完整指南》在办公室或家庭局域网中快速共享文件时,许多人会选择第三方工具或云存储服务,但这些方案往往存在隐私泄露风险或需要复杂配置,下面我们就来看看如何使用Py... 目录一、android基础版:HTTP文件共享的魔法命令1. 一行代码启动HTTP服务器2. 关键参

Python对接支付宝支付之使用AliPay实现的详细操作指南

《Python对接支付宝支付之使用AliPay实现的详细操作指南》支付宝没有提供PythonSDK,但是强大的github就有提供python-alipay-sdk,封装里很多复杂操作,使用这个我们就... 目录一、引言二、准备工作2.1 支付宝开放平台入驻与应用创建2.2 密钥生成与配置2.3 安装ali

Python获取浏览器Cookies的四种方式小结

《Python获取浏览器Cookies的四种方式小结》在进行Web应用程序测试和开发时,获取浏览器Cookies是一项重要任务,本文我们介绍四种用Python获取浏览器Cookies的方式,具有一定的... 目录什么是 Cookie?1.使用Selenium库获取浏览器Cookies2.使用浏览器开发者工具

Python实现批量提取BLF文件时间戳

《Python实现批量提取BLF文件时间戳》BLF(BinaryLoggingFormat)作为Vector公司推出的CAN总线数据记录格式,被广泛用于存储车辆通信数据,本文将使用Python轻松提取... 目录一、为什么需要批量处理 BLF 文件二、核心代码解析:从文件遍历到数据导出1. 环境准备与依赖库