两个字符串的公共子序列号

本文介绍了两个字符串的公共子序列号的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

重温最长公共子，我想知道什么是2串共同子序列的数量。我试图制定一个经常性的关系： DP的[I] [j]的重presents个子序列在最高i的第一串和j在第二结束的次数。 复发性关系的存在：

Revisiting Longest Common Subsequence, I was wondering what is the number of common subsequences of 2 strings. I tried to formulate a recurrent relation : DP[i][j] represents the number of subsequences ending at max i in first string and j in second. Recurrent relation being :

DP [I] [j]的= DP的[I-1] [J-1] + DP [i]于[J-1] + DP [I-1] [j]的在 A [1] == B〔J] （A是我的第一个字符串，而B是第二个）

DP[i][j]= DP[i-1][j-1] + DP[i][j-1] + DP[i-1][j] when A[i]==B[j] (A is my first string while B is the second)

和

DP[i][j]=DP[i-1][j]+DP[i][j-1] other wise

这是不是给正确的结果！

It is not giving correct results!

说明，如果A [1] == B〔J]，那么，我们可以添加一个[I]到每一个公共子，直到我-1和J-1，形成DP [I-1] [J-1]新的序列。同时我们必须添加由每个字符串下跌的最后一个字符构成的序列。

Explanation if A[i]==B[j], then , We can add A[i] to every common subsequence till i-1 and j-1 to form DP[i-1][j-1] new subsequences. Also We have to add the subsequences formed by dropping the last character from each string.

其他明智的，我们只能通过删除最后一个字符添加方法！

other wise we can only add the ways by dropping last characters!

如果有人能解决这个复发？ Morover，我会喜欢看到一个正式的证明。（刚刚进入看到正式证明的习惯（你可以提供一个提示，以证明它自己了。））

If someone can correct this recurrence? Morover , I will love to see a formal proof.(Just getting into the habit of seeing a formal proof(You can provide a hint to prove it myself too.))

修改：我忘了提基地情况下，我正在考虑

EDIT: I forgot to mention the base cases I was considering

DP [I] [0] = 1 所有我在一个长度

和 DP [0] [J] = 1 对于所有的j B中的长度

and DP[0][j]=1 for all j in length of B

和也

DP[0][0]=1

（表示空子）

(denoting empty subsequence)

推荐答案

DP [I-1] [J] 和 DP [I] [J-1] 应 DP [I-1] [J-1] 公共子序列，这将是重复计算。

DP[i-1][j] and DP[i][j-1] shall have DP[i-1][j-1] common sub-sequences which will be double counted.

更改复发为：

DP [I] [J] = DP [I] [J-1] + DP [I-1] [J] 在 A [1] == B〔J]

和

DP [I] [J] = DP [I-1] [J] + DP [I] [J-1] -DP [I-1] [J-1] 其他明智

说明： 在原来的关系，我刚才已经减去了一学期 DP [I-1] [J-1] 。这是因为 DP [I] [J-1] 和 DP [I-1] [J] 都包括 DP [I-1] [J-1] 。因为我们添加这两个名词，术语 DP [I-1] [J-1] 是越来越重复计算，所以我们需要一次减去它。

Explanation: In your original relations, I have just subtracted a term DP[i-1][j-1]. This is because DP[i][j-1] and DP[i-1][j] both include DP[i-1][j-1]. Since we are adding these two terms, the term DP[i-1][j-1] is getting double counted, so we need to subtract it once.