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

Question

回顾最长公共子序列，我想知道2个字符串的公共子序列的数量是多少。我试图建立一个循环关系： DP[i][j] 表示第一个字符串中以 max i 结尾、第二个字符串中以 j 结尾的子序列的数量。 循环关系是：

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

当

A[i]==B[j]

时（A是我的第一根弦，B是第二根弦）

和

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

它没有给出正确的结果！

说明如果A[i]==B[j]，那么，我们可以将A[i]添加到每个公共子序列中，直到i-1和j-1，形成DP[i-1][j-1]个新子序列。另外，我们还必须添加通过删除每个字符串的最后一个字符而形成的子序列。

否则我们只能通过删除最后一个字符来添加方式！

是否有人可以纠正这种情况？此外，我很想看到一个正式的证明。（只是养成看正式证明的习惯（你也可以提供一个提示来证明它自己。））

编辑：我忘了提及我正在考虑的基本情况

DP[i][0]=1

对于 A 长度中的所有 i

和

DP[0][j]=1

对于 B

长度中的所有 j

还有

DP[0][0]=1

（表示空子序列）

Answer 1

DP[i-1][j]

和

DP[i][j-1]

应有

DP[i-1][j-1]

公共子序列，将被重复计算。

将您的重复次数更改为：

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

当

A[i]==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]

项会被重复计算，因此我们需要将其减去一次。

Answer 2

#define MAX_LEN 101
string s1;
string s2;
int N1;
int N2;
int dp[MAX_LEN][MAX_LEN];
int GetCommomSubsequencesCount()
{
    for (int i = 0; i <= N1; i++)//N1 is size of 1st string
    {
        for (int j = 0; j <= N2; j++)//N2 is size of 2nd string
        {
            dp[i][j] = 0;
        }
    }
    for (int i = 1; i <= N1; i++)
    {
        for (int j = 1; j <= N2; j++)
        {
            if (s1[i - 1] == s2[j - 1])
            {
                dp[i][j] = 1 + dp[i][j - 1] + dp[i - 1][j];                    
            }
            else
            {
                dp[i][j] =  dp[i][j - 1] + dp[i - 1][j] - dp[i-1][j-1];
            }
        }
    }
    return dp[N1][N2];
}

说明：

dp[i][j] 分别是大小为 i 和 j 的两个字符串的公共子序列的数量

情况 1：s1[i-1] == s2[j-1]

所有先前的公共子序列都会加倍，因为它们会附加一个字符。 dp[i][j-1] 和 dp[i-1][j] 都包含 dp[i-1][j-1]，因此它在我们的递归中被添加两次，从而将 dp[i-1][j-1] 的计数加倍所有先前的公共子序列。 递归加1是为了最新的字符匹配：由s1[i-1]和s2[j-1]组成的公共子序列

情况 2：s1[i-1] != s2[j-1]

这里我们减去 dp[i-1][j-1] 一次，因为它同时存在于 dp[i][j - 1] 和 dp[i - 1][j] 中，并且被添加两次。

我认为这些重复更容易吸收，因为它们不依赖于空子序列。

Answer 3

当我想到要回来时我很兴奋(1<< LCS(str1, str2) lcs，最长公共子序列。

我无法弄清楚为什么会失败。