algorithm - 不同的子序列 DP 解释

Question

来自 LeetCode

Given a string S and a string T, count the number of distinct subsequences of T in S.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).

Here is an example: S = "rabbbit", T = "rabbit"

Return 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];
}

Answer 1

首先，尝试自己解决问题，想出一个简单的实现:

假设S.length = m和 T.length = n .让我们写S{i}对于 S 的子串从 i 开始.例如，如果 S = "abcde" , S{0} = "abcde" , S{4} = "e" , 和 S{5} = "" .我们对 T 使用类似的定义.

让N[i][j]是 S{i} 的不同子序列和 T{j} .我们对N[0][0]感兴趣(因为它们都是完整的字符串)。

有两种简单的情况:N[i][n]对于任何 i和 N[m][j]对于 j<n . "" 有多少个子序列在一些字符串中 S ？正好 1. 有多少 T在"" ？只有 0 个。

现在，给定一些任意的 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 table 。我们首先需要设置表格的边界:

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];
}

到

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];
    }
}