最長公共子序列問題： 給定兩個字符串A嫉称、B闲询，求A與B的最長公共子序列（子序列不要求是連續(xù)的）?
舉例：?
字符串A： abcdef?
字符串B：cd12334?
輸出：cd
解題思路
這個問題是動態(tài)規(guī)劃的問題豌熄，可以用動態(tài)規(guī)劃表來進(jìn)行求解
dp[i][j]:定義為a串第i位置b串第j位置以前的兩個序列的最大的LCS，那么顯而易見趟畏，dp[0][0]=0,dp[n][m]就是我們要求的最大值
狀態(tài)轉(zhuǎn)移方程：
1.a[i]=b[j] ? dp[i][j]=dp[i-1][j-1]+1 ?
2.a[i]!=b[j] ? dp[i][j]=max(dp[i-1][j],dp[i][j-1])
ps：當(dāng) i , j 位置的字符串相同的時候，我們i 怨绣，j 位置的值就是以前的LCS位置（i-1，j-1）加1
? ? ? ? 當(dāng)I 拷获，j的字符串不相同時候篮撑，LCS的長度不會增加，但是我們有兩種選擇匆瓜，就是i赢笨，j-1位置和i，j-1位置的值驮吱，我們選取最大的LCS作 ? ? 為當(dāng)前的LCS即可
動態(tài)規(guī)劃
核心代碼
for(int i=1;i<=n;i++){
? ??for(int j=1;j<=m;j++){
? ??????if(a[i]==b[j]) dp[i][j]=dp[i-1][j-1]+1;
? ??????else dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
????}
}
