首页 > 编程学习 > dp(动态规划)之最长公共子序列

dp(动态规划)之最长公共子序列

发布时间:2022/10/5 17:33:58

今天分享一道比较典型的dp问题:
问题描述:

我们有两个字符串m和n,如果它们的子串a和b内容相同,则称a和b是m和n的公共子序列。子串中的字符不一定在原字符串中连续。
例如字符串“abcfbc”和“abfcab”,其中“abc”同时出现在两个字符串中,因此“abc”是它们的公共子序列。此外,“ab”、“af”等都是它们的字串。
现在给你两个任意字符串(不包含空格),请帮忙计算它们的最长公共子序列的长度。

来源链接:https://www.nowcoder.com/questionTerminal/9ae56e5bdf4f480387df781671db5172
来源:牛客网

解题思想:首先这道题用常规思维来想,很容易让人思考越陷越深,因为两个字符串的比较情况太多了,这道题我拿到的第一反应就是要拿dp解决,首先dp最难的就是要找到他的初始已知条件和dp递推公式,这道题呢用dp状态矩阵来解决,首先dp状态矩阵就表示的是两个字符串各个位的最长公共子序列长度。
针对题里的输入的例子的图例如下:
在这里插入图片描述
首先初始条件可以是dp [0] [0] ,看两个字符串下标都为0时的字符是否是相等的,如果相等的话,则dp[0][0]为1,否则为0 ;接下来要处理的就是两个边界特殊情况比如i=0,j为任意 这时处于矩阵的最上面一行,这时dp[0][j]就只会是他前面的一个状态dp[0][j-1]的结果以及他自身dp[0][j]的结果(自身的这个dp[0][j]可以要看此时的s1[0]和s2[j]是否相等,相等则为1,否则为0)有关;令一种情况i为任意,j=0的情况同上;这两个边界情况处理完后,就是一般情况了dp[i][j] = max(dp[i-1][j],dp[i][j-1]),因为此时这两种情况都可以到dp[i][j],所以要取最大的一个,中间当然也会出现s1[i]=s2[j]的情况,这时就是dp[i-1][j-1]+1和dp[i][j]本身之间取最大值,因为如果此时s1[i]=s2[j]的话则dp[i-1][j-1](s1的i和s2的j同时-1之后的dp状态)加上一个字符的话就是dp[i][j],所以此时dp[i][j]=max(dp[i-1][j-1]+1,dp[i][j])。

在思考这个问题的时候i,j就s1和s2的下标!!!
全程需要注意数组下标不要越界!!!

实现代码:

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;int main()
{string s1, s2;while (cin >> s1 >> s2){int len1 = s1.size();int len2 = s2.size();vector<vector<int>> dp(len1, vector<int>(len2, 0));dp[0][0] = (s1[0] == s2[0]) ? 1 : 0;  //初始已知条件for (int i = 1; i < len1; i++){       //特殊上边界dp[i][0] = (s1[i] == s2[0]) ? 1 : 0;dp[i][0] = max(dp[i - 1][0], dp[i][0]);}for (int j = 1; j < len2; j++){      //特殊左边界dp[0][j] = (s1[0] == s2[j]) ? 1 : 0;dp[0][j] = max(dp[0][j - 1], dp[0][j]);}for (int i = 1; i < len1; i++){      //一般情况for (int j = 1; j < len2; j++){dp[i][j] = max(dp[i - 1][j],dp[i][j - 1]);if (s1[i] == s2[j])dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);}}cout << dp[len1 - 1][len2 - 1] << endl;   //返回当然是dp[len1-1][len2-1],注意下标一定不要越界}return 0;
}

运行结果:
在这里插入图片描述


本文链接:https://www.ngui.cc/el/1524707.html
Copyright © 2010-2022 ngui.cc 版权所有 |关于我们| 联系方式| 豫B2-20100000