leet_115

题目链接

题意

给定一个字符串 S 和一个字符串 T，计算在 S 的子序列中 T 出现的个数。

一个字符串的一个子序列是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）

题解

暴力解法

暴力方法就是DFS搜索，每搜到一种可能就+1，代码类似于：

func search(s,t string, t_idx int, ans *int) {
    // 递归边界
    if t_idx == len(t)-1 {
        for i:=0; i<len(s); i++ {
            if t[t_idx] == s[i] {
                *ans ++
            }
        }
        return
    }
    for i:=0; i<len(s); i++ {
        if t[t_idx] == s[i] {
            search(s[i+1:], t, t_idx+1, ans)
        }
    }
}

这种暴力方法显然不符合hard题的风格

动态规划

其实这道题DP很好设计，而且很好优化。 当看t[i]==s[j]时，t[0..i]是不是s[0..j]的子序列时，如果发现t[0..i-1]是s[0..k]的子序列，那么t[0..i]也就是s[0..j]的子序列。我们枚举这个k，每找到一个t[0..i-1]是s[0..k]的子序列，就累加起来得到T，这就说明s[0..j]中一共有T个子序列等于t[0..i]。

所有状态转移方程很好想：

f(i,j) = ∑f(i-1,k) (t[i] == s[j])

到这里似乎就OK了，但是有一个非常容易发现的优化之处，即： 我们每次转移时，只和f(i-1, x)有关，和f(i-2, x)无关，也就是说我们枚举到i时只需要i-1的状态。因此，我们可以把f(i,j)优化成f(0|1, j)

到这里是不是就完事儿了呢？其实还可以继续优化空间，怎么优化？

看下面代码:

for i:=0; i<len(t); i++ {
    for j:=i; j<len(s); j++ {
        if t[i] == s[j] {
            f(i,j) = ∑f(i-1, 0..j-1)
        }
    }
}

当我们更新f(i,j)时，其实你会发现并不是都和f(i-1, xxx)有关，只和f(i-1, 0..j-1)有关。 所以我们可不可以来一点骚操作，只用一维数组f(j)来表示状态，然后倒着枚举，也就是for j:=len(s)-1; j>=0; j--。倒着枚举有什么用呢？ 仔细想一想上面的结论，更新f(i,j)只与f(i-1, 0..j-1)有关。如果我倒着枚举，当j==m时，f(0..m-1)其实还存着上一轮的f值，也就是f(i-1, 0..m-1)的值。

因此我们可以利用倒序枚举把空间压缩到一维。

但是压缩到一维就真的好么？这个其实也得分情况讨论，你别忘了CPU的高速缓存，倒着枚举有时候会把数组靠后的内存端拿去填充L1，这时候如果L1不命中的话，就有点得不偿失了，因为用0|1滚动的空间已经很不错了。

我代码里分别给出了0|1滚动的倒序枚举两种解法，两种实现其实只有细微的差别，如果N特别大的时候，优化成一维还是有收益的，有兴趣可以看一看