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

Question

重温最长公共子序列，我想知道2个字符串的公共子序列数是多少。我试图制定一个经常性的关系： DP[i][j] 表示第一个字符串以最大 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

结果不正确！

说明 if A[i]==B[j], then , 我们可以将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] ，因此它在我们的循环中被添加了两次，它负责将所有以前的公共子序列。递归加1是为了最新的字符匹配：由s1[i-1]和s2[j-1]

组成的公共子序列

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

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

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

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

Number of Common sub sequences of two strings

language-agnostic

algorithm

dynamic-programming