【題目描述】
Given two strings, find the longest common subsequence (LCS).
Your code should return the length ofLCS.
給出兩個字符串址貌，找到最長公共子序列(LCS)铐拐，返回LCS的長度徘键。
【題目鏈接】
www.lintcode.com/en/problem/longest-common-subsequence/
【題目解析】
求最長公共子序列的數(shù)目，注意這里的子序列可以不是連續(xù)序列遍蟋，務(wù)必問清楚題意吹害。求『最長』類的題目往往與動態(tài)規(guī)劃有點(diǎn)關(guān)系，這里是兩個字符串匿值，故應(yīng)為雙序列動態(tài)規(guī)劃赠制。
這道題的狀態(tài)很容易找，不妨先試試以f[i][j]表示字符串A 的前i位和字符串 B 的前j位的最長公共子序列數(shù)目挟憔，那么接下來試試尋找其狀態(tài)轉(zhuǎn)移方程钟些。從實際例子ABCD和EDCA出發(fā)，首先初始化f的長度為字符串長度加1，那么有f[0][0] = 0,f[0][*] = 0,f[*][0] = 0, 最后應(yīng)該返回f[lenA][lenB]. 即 f 中索引與字符串索引對應(yīng)(字符串索引從1開始算起)，那么在A 的第一個字符與 B 的第一個字符相等時笼才，f[1][1] = 1 + f[0][0], 否則f[1][1] = max(f[0][1], f[1][0])泻轰。
推而廣之，也就意味著若A[i] == B[j], 則分別去掉這兩個字符后裕偿，原 LCS 數(shù)目減一，那為什么一定是1而不是0或者2呢？因為不管公共子序列是以哪個字符結(jié)尾宗弯，在A[i] == B[j]時LCS 最多只能增加1. 而在A[i] != B[j]時，由于A[i]或者B[j]不可能同時出現(xiàn)在最終的 LCS 中搂妻，故這個問題可進(jìn)一步縮小蒙保，f[i][j] = max(f[i - 1][j], f[i][j - 1]). 需要注意的是這種狀態(tài)轉(zhuǎn)移方程只依賴最終的 LCS 數(shù)目，而不依賴于公共子序列到底是以第幾個索引結(jié)束欲主。
【參考答案】
