首页 > 其他分享 >编辑距离 动态规划又一题型

编辑距离 动态规划又一题型

时间:2024-01-23 13:13:23浏览次数:29  
标签:题型 操作数 相等 else 编辑 数组 动态 dp

这种题目一般是给两个字符串,找一些特性或进行一些操作。
根据题目意思设置二维数组,行列长度为两个字数组的长度加1。之所以加一是为了留空间对空字符串进行讨论。
递推式就是两个数组中如果元素相等怎么样,不相等又怎么样。

最长公共子序列:

点击查看代码
if (text1[i - 1] == text2[j - 1]) {
    dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
相等的话就是数目加一,如果不相等就不看当前数组的字符比较后面,因为有两个数组就要取其中较大的。

不同子序列:

这题base就是不考虑长子串的当前内容,往后看。dp[i-1][j].
如果长短数组当前元素相等就要还有加上dp[i-1][j-1]的情况的数量。

编辑距离:

有三种操作增删改,但其实增和删效果是一样的。
删除操作:

点击查看代码
if (word1[i - 1] == word2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);
                }
如果相等两数组就比较下一个,不相等是只需删除一个数组中的元素,同时操作数就要加1,因为有两个数组操作数取其中较小那个。 替换操作: dp[i - 1][j - 1]+1; 因为替换后就相等了,两数组就可以比较下一个,但操作数要加1。

标签:题型,操作数,相等,else,编辑,数组,动态,dp
From: https://www.cnblogs.com/yun-che/p/17982219

相关文章

  • 动态 DP
    序列——线段树维护矩阵转移首先,我们需要普通DP方程改为矩阵乘法或广义矩阵乘法形式,可能会增加一些状态,然后用线段树维护矩阵乘法即可。这个模型推荐使用横向量乘方阵的形式,可以直接从左往右乘。树——重链剖分原理首先,记录每个节点的轻儿子对这个节点DP数组的贡献,然后用......
  • 【动态规划】正则表达式
    目录1.题目2.应用2.1.Leetcode10.正则表达式匹配题目解题思路代码实现1.题目题目列表:序号题目难度110.正则表达式匹配困难2.应用2.1.Leetcode10.正则表达式匹配题目10.正则表达式匹配解题思路设\(dp[i][j]\)表示\(s\)的前\(i\)个字符与......
  • 深入分析若依数据权限@datascope (注解+AOP+动态sql拼接) 【循序渐进,附分析过程】
    除了我们平时都知道的路由权限(即对接口的访问权限外),在日常生产开发中,我们还应该有对数据的访问权限。在若依这个框架中,通过角色中的数据范围这个属性来对数据权限进行控制。对应实体类:深入分析一个用户肯定是有一种角色的,也肯定是隶属于一个部门的。这里咱们就以用户在......
  • 动态规划(9) 编辑距离最终版
    目录115不同的子序列583.两个字符串的删除操作编辑距离115不同的子序列dp数组的含义:dp[i][j]以i-1结尾的s中包含有多少个以j-1为结尾的tdp初始化:dp[0][0]空字符串中有多少个空字符串,显然1个dp[i][0]以i-1为结尾的s中包含有多少个空字符串,也是1个递推公式:显然需要考虑s[i......
  • 动态规划(8) 编辑距离
    目录1035不相交的线53最大子数组和392判断子序列1035不相交的线弄清楚在求什么,实际上是在求最长公共子序列classSolution{public:intmaxUncrossedLines(vector<int>&nums1,vector<int>&nums2){intn=nums1.size();intm=nums2.size();......
  • 华企盾DSC:外发文件设置编辑权限 阅读次数 阅后即焚 文件过期
    互联网时代,信息流通迅速,一份关键的内部文件一旦外泄,可能毁掉公司数月、甚至数年的努力。企业多次碰壁后终于发现,仅仅依靠员工层层审批、体系内控制,已难以防止数据泄密这一严重问题。更为糟糕的是,一旦文件发送出去,系统往往不能有效地控制未授权阅读的发生。痛定思痛,企业用户渴望有......
  • 动态规划- leecode 122
    Problem:122.买卖股票的最佳时机II目录思路解题方法复杂度Code思路仍然是一道比较简单的动态规划,但是一上手做还是没理清楚状态是什么。一天的状态只有两种,持有股票和没有股票,这样就可以列出状态转移方程\(dp[i][j]=max(dp[i-1][j],dp[i-1][j*]+或-price[i])\),这里的j表......
  • 二维动态规划+子集和
    题目:查看代码#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;constintN=1e3+7;constllmod=1e5+7;intn,s;intdp[N][N],a[N];intmain(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n;for(in......
  • 模拟jdk动态代理(完整版)
    实现思路1:定义一个字符串s2:加载s利用流生成对应的java文件3:通过类加载器加载java文件生成class文件4:通过class生成代理对象5:测试成功我使用过jdk代理的场景1:通过拦截request对象,代理其中的get参数的方法来过滤敏感词2:通过阅读aop源码发现,底层用的也是动态代理(jdk,cglib)3:jdk代......
  • Qt如何调用VS编写的动态链接库(dll文件)
     下面是我在VS编译器上写的一个简单的dll文件,关于dll文件如何编写,我就不再赘述了。.h文件#ifndef_MYDLL_H#define_MYDLL_H#ifdefMYDLL_EXPORTS#defineMYDLL_API__declspec(dllexport)#else#defineMYDLL_API__declspec(dllimport)#endifextern"C"MYDLL_......