字符串上的动态规划算法应用

「爱情、让人受尽委屈。」 2022-09-30 07:29 121阅读 0赞

经常遇到字符串上的相关问题，有涉及到一个字符串和两个字符串的，它们解题方式类似，都是采用动态规划算法来解决，这里做一个整理归纳。

1.求整数序列中的最长增长子序列，和字符串问题类似，也是用动态规划的算法来解决，具体参见我之前的一篇博客：[http://blog.csdn.net/na\_beginning/article/details/53611008][http_blog.csdn.net_na_beginning_article_details_53611008]

2.求两个字符串的最长公共子序列。

例如，字符串 s1 = zxyxyz 和 字符串 s2 = xyyzx，s1和s2的最长公共子序列是 xyyz。

可以用动态规划的算法来解决此问题，L\[i\]\[j\] 表示字符串 s1 中前 i 个字符和 字符串 s2 中前 j 个字符的最长公共子序列，这和原问题是一样的子问题，只是问题规模更小，即满足动态规划的最优子结构性质，初始化 L\[i\]\[0\] = 0, L\[0\]\[j\] = 0, 然后计算 L\[i\]\[j\], 如果 s1\[i\] = s2\[j\]，那么 L\[i\]\[j\] = L\[i-1\]\[j-1\] + 1; 如果 s1\[i\] != s2\[j\]，那么 L\[i\]\[j\] = max(L\[i\]\[j-1\], L\[i-1\]\[j\])。

代码：

#include <iostream>
    #include <string>
    using namespace std;
    
    void test1()
    {
        string s1, s2;
        while(cin >> s1 >> s2)
        {
            int **dp = new int*[s1.length()+1];
            for(int i = 0; i < s1.length()+1; i++)
            {
                dp[i] = new int[s2.length()+1];
            }
            for(int i = 0; i < s1.length()+1; i++)
                dp[i][0] = 0;
            for(int i = 0; i < s2.length()+1; i++)
                dp[0][i] = 0;
            for(int i = 1; i < s1.length()+1;i++)
            {
                for(int j = 1; j < s2.length()+1; j++)
                {
                    if(s1[i-1] == s2[j-1])
                        dp[i][j] = dp[i-1][j-1] + 1;
                    else
                        dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
                }
            }
            cout << dp[s1.length()][s2.length()] << endl;
            for(int i = 0; i < s1.length()+1; i++)
            {
                delete dp[i];
                dp[i] = 0;
            }
            delete [] dp;
            dp = 0;
        }
    }
    
    int main()
    {
        test1();
        return 0;
    }

输入示例：

zxyxyz
    xyyzx

输出示例：

3.求两个字符串之间的编辑距离。

来自于华为的一道编程题。

问题描述：  
Levenshtein 距离，又称编辑距离，指的是两个字符串之间，由一个转换成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。编辑距离的算法是首先由俄国科学家Levenshtein提出的，故又叫Levenshtein Distance。

Ex：

字符串A:abcdefg

字符串B: abcdef

通过增加或是删掉字符”g”的方式达到目的。这两种方案都需要一次操作。把这个操作所需要的次数定义为两个字符串的距离。

要求：  
给定任意两个字符串，写出一个算法计算它们的编辑距离。

**输入描述：**

输入两个字符串

**输出描述：**

得到计算结果

**输入示例：**

abcdefg
    abcdef

**输出示例：**

问题分析：这个问题也很适合使用动态规划算法来解决，对于字符串 s1 和 s2 而言，dist\[i\]\[j\] 表示 s1 的前 i 个字符和 s2 的前 j 个字符之间的编辑距离，这是原问题的子问题，而且问题性质一样，满足动态规划的最优子结构性质。 当 s1\[i\] == s2\[j\] 时，dist\[i\]\[j\] = dist\[i-1\]\[j-1\]；当 s1\[i\] != s2\[j\] 时，dist\[i\]\[j\] = min(dist\[i-1\]\[j-1\]+1, min(dist\[i\]\[j-1\]+1, dist\[i-1\]\[j\]+1))，这三种情况分别对应在dist\[i-1\]\[j-1\]基础上将 s1 第 i 个字符和 s2 第 j 个字符进行替换的操作，在dist\[i\]\[j-1\]基础上删除或插入 s2 的第 j 个字符，在dist\[i-1\]\[j\]基础上插入或者删除 s1 的第 i 个字符。

代码：

#include <iostream>
    #include <string>
    using namespace std;
    
    void test1()
    {
        string s1, s2;
        while(cin >> s1 >> s2)
        {
            int **dist = new int*[s1.size()+1];
            for(int i = 0; i < s1.size()+1; i++)
            {
                 dist[i] = new int[s2.size()+1];
            }
            for(int i = 0; i < s1.size()+1; i++)
            {
                 dist[i][0] = i;
            }
            for(int i = 1; i < s2.size()+1; i++)
            {
                 dist[0][i] = i;
            }
            for(int i = 1; i < s2.size()+1; i++)
            {
                 for(int j = 1; j < s1.size()+1;j++)
                 {
                    if(s1[j-1] == s2[i-1])
                        dist[j][i] = dist[j-1][i-1];
                    else
                        dist[j][i] = min(min(dist[j-1][i]+1, dist[j][i-1]+1), dist[j-1][i-1]+1);
                 }
            }
            cout << dist[s1.size()][s2.size()] << endl;
    
            for(int i = 0; i < s1.size()+1; i++)
            {
                 delete dist[i];
                 dist[i] = 0;
            }
            delete [] dist;
            dist = 0;
        }
    }
    
    int main()
    {
        test1();
        return 0;
    }

[http_blog.csdn.net_na_beginning_article_details_53611008]: http://blog.csdn.net/na_beginning/article/details/53611008