不同的子序列DP解释

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

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]for any i和N[m][j]for 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表格.我们首先需要设置表的边界:

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