首页 > 其他分享 >动态规划(9) 编辑距离最终版

动态规划(9) 编辑距离最终版

时间:2024-01-22 11:23:21浏览次数:40  
标签:结尾 int 编辑 最终版 word1 word2 字符串 动态 dp

目录

115不同的子序列

  1. dp数组的含义:dp[i][j]以 i-1结尾的s中包含有多少个以j-1为结尾的t
  2. dp初始化:dp[0][0]空字符串中有多少个空字符串,显然1个 dp[i][0]以i-1为结尾的s中包含有多少个空字符串,也是1个
  3. 递推公式: 显然需要考虑 s[i-1]==t[j-1]
  • s[i-1]t[j-1] dp[i][j]=dp[i-1][j-1]+dp[i-1][j],因为也需要考虑到前面的dp数组已经满足条件
    比如bagg和bag s[3]
    t[2]可以通过bag ba推导出一个满足的,也要加入bag bag来推导
  • s[i-1]!=t[j-1] dp[i][j]=dp[i-1][j]
class Solution {
public:
    int numDistinct(string s, string t) {
        //dp数组的含义dp[i][j]以 i-1结尾的s中包含有多少个以j-1为结尾的t
        int n=s.length();
        int m=t.length();
        vector<vector<long long>> dp(n+1,vector<long long>(m+1,0));
        for(int i=0;i<=n;i++)
        {
            dp[i][0]=1;
        }
        for(int i=1;i<=m;i++)
        {
            dp[0][i]=0;
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(s[i-1]==t[j-1])
                {
                    dp[i][j]=(dp[i-1][j-1]+dp[i-1][j])%1000000007;
                }
                else{
                    dp[i][j]=dp[i-1][j];
                }
            }
        }
        return dp[n][m];
    }
};

583. 两个字符串的删除操作

主要是递推公式

  1. 如果字符相等,那么dp[i][j]=dp[i-1][j-1]
  2. 如果不等
  • 删word1,即把当前word1[i]给删了,dp[i][j]=dp[i-1][j]+1
  • 删word2,dp[i][j]=dp[i][j-1]+1
class Solution {
public:
    int minDistance(string word1, string word2) {
        int n = word1.length();
        int m = word2.length();
        // dp含义,以i-1为结尾的word1变到以j-1为结尾的word2需要的操作步数
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
        // dp初始化
        //显然,从长度为x的字符串,变成长度为0的字符串,需要删除x个字符
        for (int i = 0; i <= n; i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j <= m; j++) {
            dp[0][j] = j;
        }
        // dp推导
        // word1[i]==word2[j] 挺好,不用变了,dp[i][j]=dp[i-1][j-1]

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                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);
                }
            }
        }
        return dp[n][m];
    }
};

编辑距离

题目的初始化和dp定义和之前的题目都差不多
主要是递推公式中不相等的情况

当word1[i]!=word2[j]时

dp[i][j]=以下三个中的最小值

  1. dp[i-1][j-1]+1代表换了一个元素,比如bag bae 只要替换一下就能得到相同的元素
  2. dp[i-1][j]+1 代表删了word1[i-1]元素
  3. dp[i][j-1]+1 代表删了word2[j-1]元素
class Solution {
public:
    int minDistance(string word1, string word2) {
        //dp[i][j]:以i-1为结尾的字符串word1,和以j-1位结尾的字符串word2,想要达到相等,所需
        //要删除元素的最少次数。
        vector<vector<int>> dp(word1.size()+1,vector<int>(word2.size()+1,0));
        for(int i=0;i<=word1.size();i++)
        {
            dp[i][0]=i;
        }
        for(int j=0;j<=word2.size();j++)
        {
            dp[0][j]=j;
        }
        for(int i=1;i<=word1.size();i++)
        {
            for(int j=1;j<=word2.size();j++)
            {
                //相等,不操作
                if(word1[i-1]==word2[j-1])
                {
                    dp[i][j]=dp[i-1][j-1];
                }
                //不相等,增删换
                else
                {
                    dp[i][j]=min(dp[i-1][j],min(dp[i][j-1],dp[i-1][j-1]))+1;
                }
            }
        }
        return dp[word1.size()][word2.size()];
    }
};

标签:结尾,int,编辑,最终版,word1,word2,字符串,动态,dp
From: https://www.cnblogs.com/liviayu/p/17979653

相关文章

  • 动态规划(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_......
  • 动态规划--摆花(二维dp)
    #include<iostream>usingnamespacestd;//dp[i][j]表示第i种花位置,第j个位置为止longlongintdp[120][120];longlonginta[160];intmain(){intn,m;cin>>n>>m;//n种花m盆for(inti=1;i<=n;i++){cin>>a[i];}dp[0][0]=1;for(inti=1;i<=n;......
  • spring--JDK动态代理的实现原理
    JDK动态代理的实现原理涉及到Java的反射机制。它允许在运行时动态创建一个代理类,这个代理类实现了一组接口,并将所有方法调用转发到一个InvocationHandler实例。下面是JDK动态代理的实现原理的详细步骤:定义接口:首先,定义一个或多个接口,这些接口声明了需要被代理的方法。......
  • spring--CGLIB动态代理的实现原理
    CGLIB(CodeGenerationLibrary)是一个强大的、高性能、高质量的代码生成库,它可以在运行时扩展Java类和实现Java接口。CGLIB动态代理是基于继承的方式来实现的,它不需要接口,可以代理普通类。以下是CGLIB动态代理的实现原理:继承:CGLIB动态代理通过继承目标类来创建子类,并在......
  • spring--JDK动态代理和CGLIB代理的区别
    JDK动态代理和CGLIB代理是Java中常用的两种动态代理实现方式,它们各有特点和适用场景:JDK动态代理:JDK动态代理是基于接口的代理方式,它使用Java反射机制来创建代理对象,并要求目标对象实现一个或多个接口。在代理过程中,JDK动态代理会创建一个实现了目标对象所有接口的代......