最長公共子序列長度是編輯距離的另外一種表示方法。只允許添加、刪除字符兩種慚怍。它表征的是兩字符串之間的相似度。
解決思路是：
如果a[i]=b[j]，則 公共子序列長度加1，繼續(xù)考察a[i+1]和b[j+1]。
如果a[i]!=b[j]，則刪除a[i]或者在b[j]前面添加字符a[i]，繼續(xù) 考察a[i+1]和b[j]；
或者 刪除b[j]或者在a[i]前面添加字符b[j]，繼續(xù)考察a[i]和b[j+1]。

反過來我們可以說要想求a[0…i]和b[0…j]的最長公共子序列長度max_lcs(i,j)，只能從以下三種狀態(tài)過來：（i-1,j-1） (i-1,j) 和(i,j-1)

如果：a[i]==b[j]，那么：max_lcs(i, j) 就等于： max(max_lcs(i-1,j-1)+1, max_lcs(i-1, j), max_lcs(i, j-1))；如果：a[i]!=b[j]，那么：max_lcs(i, j) 就等于： max(max_lcs(i-1,j-1), max_lcs(i-1, j), max_lcs(i, j-1))；其中 max 表示求三數(shù)中的最大值。 public int lcs(char[] a, int n, char[] b, int m) {int[][] maxLcs = new int[n][m];for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(i==0 && j==0){maxLcs[0][0] = (a[0]==b[0]?1:0);}else{maxLcs[i][j] = Integer.MIN_VALUE;if(i>0 && j>0){maxLcs[i][j] = Math.max(maxLcs[i][j],maxLcs[i-1][j-1]+(a[i]==b[j]?1:0));}if(j>0){maxLcs[i][j] = Math.max(maxLcs[i][j],maxLcs[i][j-1]);}if(i>0){maxLcs[i][j] = Math.max(maxLcs[i][j],maxLcs[i-1][j]);}}}}return maxLcs[n-1][m-1];}

總結(jié)

以上是生活随笔為你收集整理的动态规划——最长公共子序列长度的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。