首页 > 其他分享 >编辑距离 | 动态规划

编辑距离 | 动态规划

时间:2024-11-02 13:46:03浏览次数:3  
标签:字符 include int 距离 编辑 long 101 字符串 动态

设A和B是两个字符串,求将字符串A转换为字符串B的最少操作次数。字符操作共有如下三种:

      (1)删除一个字符。

      (2)插入一个字符。

      (3)将一个字符改为另一个字符。

  如A = “kitten”、 B = “sitting“,求编辑距离。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iomanip>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include <functional>
using namespace std;
typedef long long ll;

int i,j;
int dp[101][101]={{0}};
string a,b;

main()
{
    cin >> a >> b;
    for(i=0;i<=a.size();i++){
        dp[i][0]=i;
    }
    for(i=0;i<=b.size();i++){
        dp[0][i]=i;
    }
    for(i=1;i<=a.size();i++){
        for(j=1;j<=b.size();j++){
            if(a[i-1]==b[j-1]){
                dp[i][j]=dp[i-1][j-1];
            }
            else{
                dp[i][j]=min(dp[i-1][j],dp[i-1][j-1]);
                dp[i][j]=min(dp[i][j],dp[i][j-1])+1;
            }
        }
    }
    cout << dp[a.size()][b.size()] << "\n";
}

标签:字符,include,int,距离,编辑,long,101,字符串,动态
From: https://blog.csdn.net/2301_78848414/article/details/143427313

相关文章

  • 动态规划 —— 路径问题-地下城游戏
    1. 地下城游戏题目链接:174.地下城游戏-力扣(LeetCode)https://leetcode.cn/problems/dungeon-game/description/ 2. 算法原理 状态表示:以莫一个位置位置为结尾或者以莫一个位置为起点  dp[i,j]表示:到达[i,j]位置的时候,骑士所需要的最低初始健康点数(X),这个状......
  • Latex公式_数学公式编辑
    目录数学公式编辑Displayingaformula符号与字母SymbolandAlphabet希腊字母Greekalphabet希伯来字母Hebrewalphabet二元运算符Binaryoperations二元关系符Binaryrelations几何符号Geometricsymbols逻辑符号Logicsymbols集合Sets箭头Arrows特殊S......
  • 【WCH蓝牙系列芯片】-基于CH582开发板—动态更新蓝牙广播间隔
    ------------------------------------------------------------------------------------------------------------------------------------在使用蓝牙从机的时候,从机与主机设备在建立之前一直是出于广播数据状态,在从机中广播包含有广播数据和扫描回复数据,这两个内容的总长......
  • 动态动态规划 & 全局平衡二叉树 小记
    估计这几天是正式学习ddp,所以特写笔记。DDP简介是这样一类技巧,利用广义的矩阵乘法实现单点修改权值,动态查询某个点的DP值关于矩阵乘法,广义矩阵乘法其核心思想是利用矩阵乘法具有结合律(可以使用数据结构维护)的优势序列上的Ddp先看一个例子:最大子段和,显然我们有\(f_......
  • 动态规划-回文串问题——132.分割回文串II
    1.题目解析题目来源:132.分割回文串II——力扣测试用例2.算法原理首先回文串问题一定首先需要保存每个回文子串出现的位置,即二维dp表来存储所有子字符串中符合回文子串的位置,如图1.状态表示创建一个一维dp表来存储第i个位置之前的字符串数组全部划分为回文子......
  • Go语言的动态链接库(DLL)创建和使用
    #Go语言的动态链接库(DLL)创建和使用在讨论Go语言的动态链接库(DLL)创建和使用时,核心要点包括:创建DLL的步骤、调用DLL中的函数、跨平台兼容性问题、性能优化策略。创建DLL的步骤是理解和实践Go语言动态链接库的基础,涉及编写DLL源代码、编译为DLL文件以及确保DLL在目标系统上可用。......
  • (算法)交错字符串————<动态规划>
    1.题⽬链接:97.交错字符串2.题⽬描述:3.解法(动态规划):算法思路:对于两个字符串之间的dp问题,我们⼀般的思考⽅式如下:        i.选取第⼀个字符串的[0,i]区间以及第⼆个字符串的[0,j]区间当成研究对象,结合题⽬的要求来定义「状态表⽰」;        ii.......
  • 代码随想录算法训练营第三十三天|Day33 动态规划
    62.不同路径https://programmercarl.com/0062.%E4%B8%8D%E5%90%8C%E8%B7%AF%E5%BE%84.html视频讲解:https://www.bilibili.com/video/BV1ve4y1x7Eu思路int**initDP(intm,intn){int**dp=(int**)malloc(sizeof(int*)*m);inti,j;for(i=0;i<......
  • 中电金信:GienTech动态|丰收之秋,公司多项目获得荣誉
    ​ 中电金信微电影《妙“笔”生花》获国资委表彰  ​ 近日,国务院国资委在京举行中央企业社会主义核心价值观主题微电影(微视频)展映发布活动。中电金信作品《妙“笔”生花》获评第五届中央企业社会主义核心价值观主题微电影(微视频)敬业奉献类优秀作品。该片以中国电子联......
  • (C语言)动态内存管理,柔性数组
    1.为什么存在动态内存分配动态内存管理是C语言提供给我们自主维护空间大小的能力C语言提供了一个动态内存开辟的函数:void*malloc(size_tsize);这个函数向内存申请一块连续可用的空间,并返回指向这块空间的指针。·如果开辟成功,则返回一个指向开辟好空间的指针。·......