38-最长公共子序列(dp)

　　最长公共子序列

https://www.nowcoder.com/practice/c996bbb77dd447d681ec6907ccfb488a?tpId=49&&tqId=29348&rp=2&ru=/activity/oj&qru=/ta/2016test/question-ranking

题目描述

对于两个字符串，请设计一个高效算法，求他们的最长公共子序列的长度，这里的最长公共子序列定义为有两个序列U1,U2,U3...Un和V1,V2,V3...Vn,其中Ui&ltUi+1，Vi&ltVi+1。且A[Ui] == B[Vi]。

给定两个字符串A和B，同时给定两个串的长度n和m，请返回最长公共子序列的长度。保证两串长度均小于等于300。

测试样例：

"1A2C3D4B56",10,"B1D23CA45B6A",12

返回：6

#include <bits/stdc++.h>
using namespace std;

int mp[305][305];
string s1, s2;

int fun1(int n, int m){
	if(n < 0 || m < 0)
		return 0;
	if(mp[n][m])
		return mp[n][m]; 
	if(s1[n] == s2[m]){
		return mp[n][m] = fun1(n - 1, m - 1) + 1;
	}	
	else {
		return mp[n][m] = max(fun1(n - 1, m), fun1(n, m - 1));
	}
}

int fun2(int n, int m){
	for(int i = 0; i <= n; i++){
		for(int j = 0; j <= m; j++){
			if(i == 0 || j == 0){
				mp[i][j] = 0;
			}
			else if(s1[i - 1] == s2[j - 1]){
				mp[i][j] = mp[i - 1][j - 1] + 1;
			}		
			else{
				mp[i][j] = max(mp[i - 1][j], mp[i][j - 1]);
			}
		}
	} 
	return mp[n][m];
} 

int main(){
	int n, m;

	cin >> s1 >> n;
	cin >> s2 >> m;
	
	cout << fun1(n - 1, m - 1) << endl;  //递归求解 
	cout << fun2(n, m) << endl;			 //递推求解 
	return 0;
}
/*
1A2C3D4B56 10
B1D23CA45B6A 12

6
*/