标签为 [最长公共子序列] 的文章

面试指南——最长公共子序列问题

题目 给定两个字符串,求解这两个字符串的最长公共子序列(Longest Common Sequence)。比如字符串1:BDCABA;字符串2:ABCBDAB 则这两个字符串的最长公共子序列长度为4,最长公共子序列是:BCBA /* * 以下dp[0…M-1]相当于dp[0]~dp[M-1] * str1.length = M;str2.length = N ==>生成M*N大小的dp矩阵, * dp[i][j]的含义:str1[0…i]和str2[0…j]的最长公共子序列的长度 * 从左到右,从上到下,计算dp矩阵 * 1.dp第一列即dp[0…M-1][0],dp[i][0]的含义是str1[0..i]和str2[0]的最长公共子序列的长度 * str ......