参考答案
结论：最长公共序列（LCS）用动态规划求解，状态转移依据字符是否相等。核心要点：定义dp[i][j]为串A前i个与串B前j个字符的LCS长度；若A[i-1]==B[j-1]则dp[i][j]=dp[i-1][j-1]+1；否则dp[i][j]=max(dp[i-1][j], dp[i][j-1])；初始化首行首列0，最终dp[m][n]即答案。原理：序列不要求连续，故不匹配时可来自上方或左方状态；与最长公共子串（需连续）不同，子串用一维dp且归零处理。空间可压缩至O(min(m,n))滚动数组。时间O(mn)。示例：'abcde'与'ace'的LCS为'ace'长度3。