首页 / 资讯中心 / 文章详情

经典题目（1）：编辑距离 斐波那契数列

📅 2026/6/29 19:14:55 👁️ 次浏览
经典题目（1）：编辑距离 斐波那契数列
题目一给定两个字符串 str1 和 str2 请你算出将 str1 转为 str2 的最少操作数。你可以对字符串进行3种操作1.插入一个字符2.删除一个字符3.修改一个字符。字符串长度满足 1≤n≤1000 1≤n≤1000 保证字符串中只出现小写英文字母。方法(1)在word1末尾插入word2末尾的字,然后把两个词最后一个字母抵消比较word1[0..i]和word2[0..j-1]的结果(2)在word1末尾删除一个字母(e),比较word1[0..i-1]和word2[0..j]的结果(3)将word1的最后一个字母替换成word2的最后一个字母,然后同时删除最后一个字母,比较word1[0..i-1]和word2[0..j-1]的结果这里要用到动态规划然后根据上述步骤抽取出状态转移方程要注意的是尽管题目中说str1和str2都不是空字符串在构建状态转移方程时仍然要考虑str为0的情况因为在推导第一个字符的时候要和空字符的情况进行比较代码class Solution: def editDistance(self , str1: str, str2: str) - int: # write code here mlen(str1) nlen(str2) dp[[0]*(m1) for _ in range(n1)] #n2行m1列 # 仍然需要有空字符串情况因为计算第一个字符时要使用 for i in range(m1): dp[0][i]i for i in range(n1): dp[i][0]i # 由于有了空字符串所以初始化的时候直接可以用i for i in range(1,m1): for j in range(1,n1): if str1[i-1]str2[j-1]: # 由于有空字符串比较字符串是否相等时要减一 dp[j][i]dp[j-1][i-1] else: dp[j][i]min(dp[j-1][i-1],dp[j-1][i],dp[j][i-1])1 return dp[n][m]题目一变体给定两个字符串str1和str2再给定三个整数icdc和rc分别代表插入、删除和替换一个字符的代价请输出将str1编辑成str2的最小代价。数据范围0≤∣str1∣,∣str2∣≤50000≤∣str1∣,∣str2∣≤50000≤ic,dc,rc≤10000 0≤ic,dc,rc≤10000要求空间复杂度 O(n)时间复杂度 O(nlogn)方法和上题的思路类似区别是区分三种情况加入代价代码class Solution: def minEditCost(self , str1: str, str2: str, ic: int, dc: int, rc: int) - int: # write code here mlen(str1) nlen(str2) dp[[0]*(n1) for _ in range(m1)] # m1行1 n1列2 for i in range(n1): dp[0][i]i*ic for i in range(m1): dp[i][0]i*dc for i in range(1,n1): for j in range(1,m1): if str1[j-1]str2[i-1]: dp[j][i]dp[j-1][i-1] else: dp[j][i]min(dp[j-1][i-1]rc,dp[j-1][i]dc,dp[j][i-1]ic) return dp[m][n]题目二描述方法动态规划创建状态转移方程注意 [1]*n 和 [1 for i in range(n)] 的结果是完全等价的初始化一维的不可变数据如0,None,False优先使用[0] * n因为性能最好。初始化二维数组/嵌套列表如动态规划 DP 表必须使用[[0] * m for _ in range(n)]千万不要用[[0] * m] * n否则会出现“改一行全跟着变”的 Bug。代码class Solution: def Fibonacci(self , n: int) - int: # write code here if n1 or n2: return 1 dp[1]*n for i in range(2,n): dp[i]dp[i-1]dp[i-2] return dp[n-1]

相关新闻

【紧急通知】ChatGPT Plus自动续费取消倒计时：OpenAI最新TOS第4.7条修订生效前最后48小时，教你锁定“永久免费额度+历史会话迁移”双权益

【紧急通知】ChatGPT Plus自动续费取消倒计时：OpenAI最新TOS第4.7条修订生效前最后48小时，教你锁定“永久免费额度+历史会话迁移”双权益

更多请点击： https://kaifayun.com 第一章：【紧急通知】ChatGPT Plus自动续费取消倒计时：OpenAI最新TOS第4.7条修订生效前最后48小时，教你锁定“永久免费额度历史会话迁移”双权益 OpenAI 已于 2024 年 10 月 15 日凌晨正式发布…

📅 2026/6/29 19:14:55
macos支持的画质修复软件有哪些？5款Mac剪辑横评实测

macos支持的画质修复软件有哪些？5款Mac剪辑横评实测

Mac 用户寻找画质修复工具的真实困境做短视频矩阵或老视频二创时，经常遇到素材模糊、暗光、人脸糊的问题。很多创作者在搜索 macos支持的画质修复软件 时，会发现市面上大部分专业修复工具只有 Windows 版，或者 Mac 版操作极其繁琐&#xff0c…

📅 2026/6/29 19:14:55
开关电源模块全套测试项目总结

开关电源模块全套测试项目总结

稳态性能、热测试、各类故障保护、动态负载、安规、环境可靠性、EMC、老化寿命 8 大板块一、基础稳态电气性能:电源最核心的供电质量 这部分是电源最基础指标，衡量正常工作下输出是否稳定，所有负载区间都要全覆盖轻载0.2A、中载2A、满载3A三档工况。 1.输…

📅 2026/6/29 19:09:54
智能WAF核心模块开发：从规则匹配到行为分析的Python实战

智能WAF核心模块开发：从规则匹配到行为分析的Python实战

1. 项目概述：从“规则匹配”到“智能决策”的WAF进化做网络安全开发的朋友，尤其是搞WAF（Web应用防火墙）的，肯定都经历过一个阶段：规则越写越多，维护越来越累，误报和漏报却像一对孪生…

📅 2026/6/29 20:25:22
商用密码产品密钥体系架构实战：从服务器密码机到动态口令系统

商用密码产品密钥体系架构实战：从服务器密码机到动态口令系统

1. 项目概述：商用密码产品密钥体系架构实战解析在数字化浪潮席卷各行各业的今天，数据安全与身份认证的重要性被提到了前所未有的高度。无论是我们日常的移动支付、线上办公，还是企业的核心数据交换、金融交易，背后都离不开一套坚实…

📅 2026/6/29 20:25:22
TLK10232 EVM GUI：高速串行链路开发与调试实战指南

TLK10232 EVM GUI：高速串行链路开发与调试实战指南

1. TLK10232 EVM GUI：高速串行链路开发的瑞士军刀如果你正在设计或调试基于10G以太网、XAUI这类高速串行接口的系统，那么一块功能强大的评估板和与之配套的软件就是你最得力的助手。TI的TLK10232双通道收发器评估模块（EVM）及其图形…

📅 2026/6/29 20:20:18
策划方案与脚本创作能力横评：GPT-4o vs Gemini 3.0 vs Claude 3.5 实测对比

策划方案与脚本创作能力横评：GPT-4o vs Gemini 3.0 vs Claude 3.5 实测对比

在商业化内容生产、项目策划、短视频脚本开发场景中，AI模型的创意发散能力、逻辑架构能力、落地执行能力是核心考核指标。不同大模型的训练侧重不同，在方案撰写、脚本创作场景的输出质量差距极大。 为给技术从业者、内容创作者、运营人员提供精准的模型…

📅 2026/6/29 0:00:42
蒙特卡洛离策略强化学习：工业场景下的无偏评估与稳定训练

蒙特卡洛离策略强化学习：工业场景下的无偏评估与稳定训练

1. 这不是教科书里的“蒙特卡洛离策略”，而是我在强化学习项目里亲手调通的那套逻辑“Monte Carlo Off-Policy Explained”——看到这个标题，别急着去翻Sutton那本绿皮书第5章。我带过三个工业级强化学习落地项目，从智能仓储调度到金融风控策…

📅 2026/6/29 0:00:43
Java开发者转型安全开发：从代码审计到自动化工具实践

Java开发者转型安全开发：从代码审计到自动化工具实践

1. 转型背景与核心驱动力最近几年，身边不少做Java后端开发的朋友，都开始或多或少地关注起安全开发这个方向。我自己也是从写了七八年Java业务代码，一步步转向了安全领域，现在主要做代码审计和自动化安全工具开发。这个转变不是一时…

📅 2026/6/29 0:00:43
审计来了，数据权限全开——审计走了，怎么确保权限全部关掉？

审计来了，数据权限全开——审计走了，怎么确保权限全部关掉？

引言：审计结束三个月了，审计员的权限还没关某城商行每年按照监管要求开展至少一次数据安全审计。审计期间，内审部门需要抽样检查各类业务数据——交易流水、客户信息、员工操作日志、权限配置记录。这些数据分布在不同系统中，审计…

📅 2026/6/29 4:18:42