王道机试指南 例题12.6 最长公共子序列
题目：
题目大意：
算法及思路：
动态规划。
代码：
注意上述算法中字符串s1和s2的下标从1开始，下面代码中s1和s2的下标从0开始。
#include <iostream>
#include <ostream>
#include <algorithm>
using namespace std;
int MaxSeqLen(string s1,string s2){
int m=s1.size()+1,n=s2.size()+1;//数组大小+1，方便存储s1，s2是空串时的情况
int dp[m][n];//dp[i][j]表示以s1[i-1]作为末尾和以s2[j-1]作为末尾的最长公共子序列的长度（当i=0或j=0时表示对应字符串是空串）
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(i==0 || j==0)//边界值处理
dp[i][j]=0;
else{//动态规划法求以s1[i-1]作为末尾和以s2[j-1]作为末尾的最长公共子序列的长度
if(s1[i-1]==s2[j-1])
dp[i][j]=dp[i-1][j-1]+1;
else
dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
}
}
}
return dp[m-1][n-1];
}
int main(){
string s1,s2;
while(cin>>s1>>s2){
cout<<MaxSeqLen(s1,s2)<<endl;
}
return 0;
}
运行结果：
顺丰集团工作强度 250人发布
投递三维家等公司10个岗位