题目一给定两个字符串 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]