首页 > 其他 > 详细

洛谷 题解 P1279 【字串距离】

时间:2020-01-27 23:48:21      阅读:153      评论:0      收藏:0      [点我收藏+]

\(DP\)题,无疑要考虑如下几点:

\(1.\)状态定义

\(2.\)状态转移方程

\(3.\)边界

\(4.\)目标

那我们来依次分析。

状态定义

根据题意,很简单,就是:

\(f_{i,j}\)表示\(A\)串的前\(i\)个字母与\(B\)串的前\(j\)个字母的最小距离。

状态转移方程

对于\(f_{i,j}\)来说,无疑就三种情况:

\(1.\) \(A_i\)\(B_j\)\(ASCLL\)码绝对值之差

\(2.\) \(A_i\)对应着空格

\(3.\) \(B_j\)对应着空格

显然,第一种的方程最好写:\(f_{i-1,j-1}+|A_i-B_j|\)

而第二种,由于\(A_i\)对应着空格,所以,状态一定要从\(A\)串的前\(i-1\)个字母与\(B\)串的前\(j\)个字母的最小距离推得。

所以,第二个方程为:\(f_{i-1,j}+k\)

同理,第三个方程为:\(f_{i,j-1}+k\)

\(f_{i,j}\)即为三者最小值。

边界

\(f_{i,0}\)\(f_{0,j}\)入手。

先从定义出发,\(f_{i,0}\)表示\(A\)串的前\(i\)个字母与\(B\)串的前\(0\)个字母的最小距离.

是不是很怪?

所以我们只能默认第零个字母为空格,所以:

\(f_{i,0}=f{i-1,0}+k\)

化简一下,就是:\(f_{i,0}=i*k\)

同理,\(f_{0,j}=j*k\)

目标

\(A\)串长度为\(m\), \(B\)串长度为\(n\),目标易求:\(f_{m,n}\)

\(AC\) \(Code\)

#include <iostream>
#include <string>
#include <cmath>
using namespace std;

string a, b;
int m, n, f[2010][2010], k;

int main() {
    cin >> a >> b;
    cin >> k;
    m = a.size(), n = b.size();
    a = ' '+a, b = ' '+b;// 因为string下标从零开始,所以利用string加法的特性,开头加空格
    for (int i=1; i<=m; i++)
        f[i][0] = i*k;
    for (int j=1; j<=n; j++)
        f[0][j] = j*k;
    for (int i=1; i<=m; i++)
        for (int j=1; j<=n; j++) {
            f[i][j] = 1e9; // 因为要取最小,所以初值要赋大
            f[i][j] = min(f[i-1][j-1]+abs(a[i] - b[j]), min(f[i-1][j]+k, f[i][j-1]+k));
            //求三者最小值可用min套min
        }
    cout << f[m][n] << endl; 
    return 0; // 完结撒花!
}

洛谷 题解 P1279 【字串距离】

原文:https://www.cnblogs.com/zyh-cr7/p/12237212.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!