题目大意：给定两个字符串，求他们的最长公共子序列的长度
解题思路：设字符串 a = "a0,a1,a2,a3...am-1"(长度为m), b = "b0, b1, b2, b3 ... bn-1"(长度为n)，
它们的最长公共子序列为c = "c0, c1, c2, ... ck-1"，长度为k，
dp[i][j]定义为子串 "a0,a1,...,ai-1" 和 子串"b0,b1,...,bj-1"的最长公共子序列，那么dp[m][n]即为所求结果。
dp[i][j]即a的前i个字母和b的前j个字母的最长公共子序列
接下来说明dp数组的更新过程,
首先 dp[i][0] 和 dp[0][j]全部初始化为0: 其中有一个子串是空串，最长公共子序列自然为0
若a,b的最后一个字母 am-1 == bn-1,则这个字母一定是c的最后一个字母(对公共子序列有贡献)，即ck-1,
那么 子串 "a0, ... am-2" 与 子串 “b0, ... bn-2”的最长公共子序列为 "c0, ... ck-2"(长度为k-1,加上最后一个字母也就是ck-1长度就是k)
若 am-1 != bn-1, 有两种情况：
<1>若am-1 != ck-1(公共子序列的最后一个字母),那么字母am-1对公共子序列就是没有贡献的,
那么它们的最长公共子序列应该等于子串"a0,a1,a2, ..., am-2" 和 "b0,b1,b2, ..., bn-1"的最长公共子序列,即dp[m-1][n];
<2>若bn-1 != ck-1, 那么字母bn对公共子序列就是没有贡献的,
那么它们的最长公共子序列就应该等于子串"a0,a1,a2, ..., am-1" 和 子串 "b0, b1, b2, ... , bn-1"的最长公共子序列,即dp[m][n-1];
因此考虑以上两种情况,若am-1 != bn-1时,取上面两种情况的最长公共子序列中较大的一个即为am-1 != bn-1时的结果
即am-1 != bn-1时, 有 dp[m][n] = MAX(dp[m-1][n], dp[m][n-1]);
初始状态: dp[0][i] 和 dp[i][0] = 0;
状态转移方程：
Ai == Bj时, dp[i][j] = dp[i-1][j-1]+1;
Ai != Bj时, dp[i][j] = MAX(dp[i-1][j], dp[i][j-1]);
/* HDU 1159 Common Subsequence --- 入门dp */
#include <cstdio>
#include <cstring> int dp[][];
char s1[], s2[];
int len1, len2; inline int MAX(int a, int b){
return a > b ? a : b;
} /*
@function: 初始化工作
@param: void
@return: void
*/
void init()
{
len1 = strlen(s1);
len2 = strlen(s2);
for (int i = ; i < len1; ++i){
dp[][i] = ;
} for (int i = ; i < len2; ++i){
dp[i][] = ;
} } int main()
{
#ifdef _LOCAL
freopen("D:\\input.txt", "r", stdin);
#endif /*
定义状态dp[i][j]表示s1前i个字符和s2的前j个字符的最长公共子序列的长度
初始化： dp[i][0] 和 dp[0][j] 全初始化为0 (i <len1, j < len2)
状态转移方程:
s1[i] == s[j]时, dp[i][j] = dp[i-1][j-1]+1
s1[i] != s[j]时, dp[i][j] = MAX(dp[i-1][j], dp[i][j-1])
*/ while (scanf("%s%s", s1, s2) == ){
init(); for (int i = ; i <= len1; ++i){
for (int j = ; j <= len2; ++j){
//详细见状态转移方程
if (s1[i - ] == s2[j - ]){
dp[i][j] = dp[i - ][j - ] + ;
}
else{
dp[i][j] = MAX(dp[i - ][j], dp[i][j - ]);
}
}//for(j)
}//for(i)
printf("%d\n", dp[len1][len2]);
}
return ;
}
相关链接：