洛谷 题解 P1279 【字串距离】

做\(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