POJ 3356 AGTC（算法导论15-5编辑距离）经典dp_poj3356-程序员宅基地

技术标签： ======动态规划====== csdn 算法导论15-5编辑距离 ACM-基础dp dp POJ 3356

POJ 3356 为算法导论原题简化版，这里只讲算法导论版编辑距离。

定义状态dp[i][j]表示将x[i……m]变为y[j……n]所需要的最小代价。

对于每一个状态，有6种操作，具体如下。

1、复制

功能：i + 1，j + 1

代价：cost1

2、替换

功能：i + 1，j + 1

代价：cost2

3、删除

功能：i + 1，j不变

代价：cost3

4、插入

功能：i不变，j + 1

代价：cost4

5、旋转

功能：i + 2，j + 2（前提是x[i] = y[j + 1]，x[i + 1] = y[j]）

代价：cost5

6、终止

功能：i = m + 1

代价：cost6

所以状态转移过程如下。

一、临界情况 j = n + 1

dp[i][j] = cost6

二、其余情况

if (x[i] == y[j] // 相等就执行复制操作

dp[i][j]= dp[i + 1][j + 1] + cost1

else // 不等就在剩余4种操作里选择一个代价最小的作为dp[i][j]

{

dp[i][j] = min(dp[i + 1][j + 1] + cost2, dp[i+ 1][j] + cost3, dp[i][j + 1] + cost4)

if (x[i] == y[j + 1] && x[i + 1]== y[j]) // 满足旋转条件就尝试旋转操作

dp[i][j]= min(dp[i + 2][j + 2] + cost5, dp[i][j])

}

算法的时间复杂度为 O(m * n)，空间复杂度为 O(m * n)。

本道题略有改变，不过大体思路一样。代码如下：

#include <cmath>
#include <ctime>
#include <cstdio>
#include <string>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>

using namespace std;

const int MAX_SIZE = 1005;
int dp[MAX_SIZE][MAX_SIZE];

int main()
{
    //freopen("1.txt", "r", stdin);

    int lenx, leny;
    string x, y;
    while (cin >> lenx)
    {
        cin >> x >> leny >> y;
        memset(dp, 0, sizeof(dp));

        for (int i = lenx; i >= 0; i--)
            for (int j = leny; j >= 0; j--)
        {
            if (i == lenx)
                dp[i][j] = leny - j;
            else if (j == leny)
                dp[i][j] = lenx - i;
            else
            {
                dp[i][j] = min(dp[i + 1][j] + 1, dp[i][j + 1] + 1);
                dp[i][j] = min(dp[i + 1][j + 1] + 1, dp[i][j]);
                if (x[i] == y[j])
                    dp[i][j] = min(dp[i + 1][j + 1], dp[i][j]);
            }
        }
        printf("%d\n", dp[0][0]);
    }
    return 0;
}

本文链接：https://blog.csdn.net/ECNU_LZJ/article/details/71213879

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

SDN前瞻传统网络架构的危机：危机“四”起-程序员宅基地

文章浏览阅读272次。本文基于SDN导论的视频而成：SDN导论在网络发展速度如此之快的今天，传统网络的架构充满了危机，主要有这四个问题(3+1)。1)传统网络的部署和管理非常困难2)分布式网络架构凸显瓶颈3)流量控制十分棘手4)可编程性本文从以上三个角度出发，结合视频内容和自己的理解进行一个阐述。为什么要介绍传统网络架构的危机？只有在了解了传统网络架构的不足与缺陷之后，才能更好的理解SDN新型网络 ..._传统网络设备如果部署在网络架构中

androidStudio突然出现不识别 AppCompactActivity的故障-程序员宅基地

文章浏览阅读263次。If the soft methods via gradle file / "Invalidate caches" and the other IDE tools do not work, use the hard way: Exit Android Studio Navig...

VirtualBox中HOST-ONLY模式下共享上网-程序员宅基地

文章浏览阅读3.7k次。VirtualBox中HOST-ONLY模式下共享上网在HOST-ONLY网络模式下，虚拟系统的网卡连接到宿主计算机的VirtualBox Host-Only Network网卡上。如果要让VirtualBox的虚拟机可以访问外网，则主系统必须共享网络连接。具体操作步骤如下：1. 通过网络连接，打开“本地连接”的属性，在“共享”选项卡下设置“

Unity3D——MonoBehaviour api函数调用时序剖析（From 圣典）_monobehaviour 时序-程序员宅基地

文章浏览阅读4.4k次，点赞2次，收藏11次。MonoBehaviour Mono行为Inherits from BehaviourMonoBehaviour is the base class every script derives from.MonoBehaviour是每个脚本的基类.Using Javascript every script automatically derives from MonoBehavi_monobehaviour 时序

pytorch label smothing-程序员宅基地

文章浏览阅读271次。论文出处："When Does Label Smoothing Help? "这篇文章指出Szegedy et al.提出了Label Smoothing. 因此我们就从Szegedy et al.的文章入手。在这里我们简称Label Smoothing为LS。标签平滑也可以被简称为LSR(Label-Smoothing Regularization)。标签平滑(label-smoothing)主要用于防止过拟合，增强模型的泛化能力。在one-hot的基础上，添加一个平滑系数ε，使得最大...

Ubuntu 入门安装-程序员宅基地

文章浏览阅读41次。写在前面的话：很少一次上这么多干货，主要是对Linux的一些基本操作，常用的软件的安装，这个其实不算什么吧，方便大家也方便我，新手们早点入门Linux，少走弯路，网上资料很多，相当于一个整合咯，都是一些琐碎的东西，大佬们可以出门左拐，谢谢！一：安装Ubuntu，Windows双系统。Ubuntu的安装还是挺傻瓜的，之前也写过一篇文章吐嘈宏碁笔记本，其实都还好，遇魔杀魔，遇鬼杀鬼，很简单的，...

随便推点

Ubuntu 使用 Docker 镜像安装 MySQL 5.7_ubuntu22.04安装mysql5.7_evak_的博客-程序员宅基地

文章浏览阅读1.2k次。Ubuntu 使用 Docker 镜像安装 MySQL 5.7安装Docker 用官方脚本自动安装curl -fsSL https://get.docker.com | bash -s docker --mirror Aliyun启动Dockerservice docker start查看所有镜像docker images拉取MySql 5.7docker pull mysql:5.7#拉取最新的 MySql docker pull mysql创建MySql容器#3380是_ubuntu22.04安装mysql5.7

根据系统签名生成一个单独的签名文件jks_根据系统的签名文件生成as用的签名文件_垚石的博客-程序员宅基地

文章浏览阅读193次。1）生成platform.pem文件openssl pkcs8 -inform DER -nocrypt -in platform.pk8 -out platform.pem(2) 生成platform.p12文件，设置别名和密码，即AS打包APK时输入的别名和密码openssl pkcs12 -export -in platform.x509.pem -out platform.p12 -inkey platform.pem -password pass:123456 -name key0._根据系统的签名文件生成as用的签名文件