原题链接： https://vjudge.net/contest/389452#problem/C
文章图片
测试样例：
Input题意： 给你两个字符串，求它们的最长公共子序列长度。
abcfbc abfcab
programming contest
abcd mnp
Output
4
2
0
Input
abcfbc abfcab
programming contest
abcd mnp
Output
4
2
0
解题思路： 这道题是一道经典的dp问题，为什么是呢？由于我们是找字符串的公共子序列长度，那么这个问题是不是可以转变为先找字符串1前 i i i个字符和字符串前 j j j个字符的公共子序列长度，再慢慢递进。由此我们也就可以找到一个状态 d p [ i ] [ j ] dp[i][j] dp[i][j]，它就代表了我们上面所说的那个状态。那么初始状态就是 d p [ 0 ] [ j ] dp[0][j] dp[0][j]或 d p [ i ] [ 0 ] dp[i][0] dp[i][0],这即是我们已经知道的结果。最终状态就是 d p [ n ] [ m ] dp[n][m] dp[n][m]，我们从初始状态一步一步推到最终状态。OK，具体看代码。
【动态规划|Longest Common Subsequence（入门dp题）】AC代码：
/*
*邮箱：unique_powerhouse@qq.com
*blog:https://me.csdn.net/hzf0701
*注：文章若有任何问题请私信我或评论区留言，谢谢支持。
*
*/
#include //POJ不支持#define rep(i,a,n) for (int i=a;
i<=n;
i++)//i为循环变量，a为初始值，n为界限值，递增
#define per(i,a,n) for (int i=a;
i>=n;
i--)//i为循环变量， a为初始值，n为界限值，递减。
#define pb push_back
#define IOS ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0)
#define fi first
#define se second
#define mp make_pairusing namespace std;
const int inf = 0x3f3f3f3f;
//无穷大
const int maxn = 1e3;
//最大值。
typedef long long ll;
typedef long double ld;
typedef pairpll;
typedef pair pii;
//*******************************分割线，以上为自定义代码模板***************************************//string s1,s2;
int dp[maxn][maxn];
int main(){
//freopen("in.txt", "r", stdin);
//提交的时候要注释掉
IOS;
while(cin>>s1>>s2){
int len1=s1.size();
int len2=s2.size();
rep(i,0,len1)dp[i][0]=0;
rep(j,0,len2)dp[0][j]=0;
rep(i,1,len1){
rep(j,1,len2){
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< 推荐阅读
- 技术|为参加2021年蓝桥杯Java软件开发大学B组细心整理常见基础知识、搜索和常用算法解析例题（持续更新...)
- 数据结构与算法|【算法】力扣第 266场周赛
- 每日一题|每日一题-解码（第十一届蓝桥杯）（简单思维）
- #|算法设计与分析（Java实现）—— 动态规划 （0-1 背包问题）
- 动态规划|暴力递归经典问题
- 动态规划|动态规划 —— 状压DP (附一些位运算小知识)
- 区间DP —— 能量项链
- 动态规划 —— 区间DP
- Codeforces|Codeforces Round #605 (Div. 3) D. Remove One Element
- acm基础|哈希has散列-字符串hash