不同的子序列动态规划解释

Question

来自LeetCode

给定字符串S和字符串T，统计S中T的不同子序列数量。

字符串的子序列是通过删除一些字符（可以没有）而不改变剩余字符相对位置而形成的新字符串。（例如，“ACE”是“ABCDE”的子序列，而“AEC”则不是）

这里有一个例子：S =“rabbbit”，T =“rabbit”

返回3。

我看到了一个非常好的DP解法，不过我很难理解它，有人能解释一下这个dp是如何工作的吗？

int numDistinct(string S, string T) {

    vector<int> f(T.size()+1);

    //set the last size to 1.
    f[T.size()]=1;

    for(int i=S.size()-1; i>=0; --i){
        for(int j=0; j<T.size(); ++j){
            f[j]+=(S[i]==T[j])*f[j+1];
            printf("%d\t", f[j] );
        }
        cout<<"\n";
    }
    return f[0];
}

- J.W.

Answer 1

首先，尝试自己解决问题并得出一个简单的实现：

假设 S.length = m，T.length = n。我们用 S{i} 来表示从 i 开始的子字符串 S。例如，如果 S = "abcde"，则 S{0} = "abcde"，S{4} = "e"，S{5} = ""。我们对 T 使用类似的定义。

令 N[i][j] 表示 S{i} 和 T{j} 的不同子序列。我们感兴趣的是 N[0][0]（因为它们都是完整的字符串）。

有两种简单情况：对于任何 i，N[i][n] 和对于任何 j

现在，给定任意的 i 和 j，我们需要找到一个递归公式。有两种情况。

如果 S[i] != T[j]，我们知道 N[i][j] = N[i+1][j]（我希望您可以自行验证此内容，我旨在详细解释上面的加密算法，而不是这个简单版本）。

如果 S[i] = T[j]，我们有一个选择。我们可以“匹配”这些字符并继续处理 S 和 T 的下一个字符，或者我们可以忽略这个匹配（就像 S[i] != T[j] 的情况一样）。由于我们有这两种选择，我们需要将它们的计数相加：N[i][j] = N[i+1][j] + N[i+1][j+1]。

为了使用动态规划找到 N[0][0]，我们需要填充 N 表。我们首先需要设置表的边界：

N[m][j] = 0, for 0 <= j < n
N[i][n] = 1, for 0 <= i <= m

由于递归关系中存在依赖性，我们可以通过向后循环 i 并向前循环 j 来填充表的其余部分。

for (int i = m-1; i >= 0; i--) {
    for (int j = 0; j < n; j++) {
        if (S[i] == T[j]) {
            N[i][j] = N[i+1][j] + N[i+1][j+1];
        } else {
            N[i][j] = N[i+1][j];
        }
    }
}

---

现在我们可以使用算法中最重要的技巧：我们可以使用一个一维数组f，并在外层循环中使用不变量：f = N[i+1]; 这是由于表格填充的方式所致。如果应用到我的算法中，这将如下：

f[j] = 0, for 0 <= j < n
f[n] = 1

for (int i = m-1; i >= 0; i--) {
    for (int j = 0; j < n; j++) {
        if (S[i] == T[j]) {
            f[j] = f[j] + f[j+1];
        } else {
            f[j] = f[j];
        }
    }
}

---

我们已经接近您提供的算法了。首先，我们不需要初始化f[j] = 0。其次，我们不需要像f[j] = f[j]这样的赋值。

由于这是C++代码，我们可以重写这段代码。

if (S[i] == T[j]) {
    f[j] += f[j+1];
}

to

f[j] += (S[i] == T[j]) * f[j+1];

就是这样。这样就得到了算法：

f[n] = 1

for (int i = m-1; i >= 0; i--) {
    for (int j = 0; j < n; j++) {
        f[j] += (S[i] == T[j]) * f[j+1];
    }
}

- Vincent van der Weele

---

@S.H. 你可以将其视为 for(int i = 0; i <= m; i++) { N[i][n] = 1; }。最大的区别在于这种方式是操作性的：我提供了一个“算法”来设置值，而帖子中的方式是声明性的：我只关心值，不关心如何实现它们。这是一种更数学化的写法。 - Vincent van der Weele

抱歉如果这是一个愚蠢的问题，但是 dp 如何确保只计算不同的子序列？ - frodo

@frodo，每个子序列都是一个精确匹配的结果：S 的某些字母与 T 的字母匹配，而有些则不匹配。该算法循环遍历 S 的字母，并在它匹配或不匹配 T 中的字母时累加结果。没有第三种选择，因此不会重复计数。希望这不会让你更加困惑;-) - Vincent van der Weele

真是一篇好的解释！在SO上并不多见算法问题得到如此高质量的回答。赞一个，希望能看到更多！ - nz_21

Answer 2

我认为答案很棒，但可能有些不正确。

我认为我们应该反向迭代i和j。然后我们将数组N更改为数组f，我们向前循环j以避免重叠上次得到的结果。

for (int i = m-1; i >= 0; i--) {
    for (int j = 0; j < n; j++) {
        if (S[i] == T[j]) {
            N[i][j] = N[i+1][j] + N[i+1][j+1];
        } else {
            N[i][j] = N[i+1][j];
        }
    }
}

- user2313762

---

我不理解你的最后一句话。你能否请再检查一下你所写的内容，确保它是有意义的？ - jbaums

我错了。写成二维数组的代码也是正确的，对于j正向循环和反向循环都是正确的。但当我们把二维数组改成一维数组时，我们必须正向循环j，否则我们无法在最新的循环（即j+1）中获得结果。最后一次循环的结果存储在数组f中，我们有"f[j] += (S[i] == T[j]) * f[j+1]"，我们正向循环j，这样我们确保在计算f[j]时不会修改f[j + 1]。 - user2313762