## Distinct Subsequences

### 描述

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.

### 代码

// Distinct Subsequences
// 二维动规+滚动数组
// 时间复杂度O(m*n)，空间复杂度O(n)
public class Solution {
public int numDistinct(String s, String t) {
int[] f = new int[t.length() + 1];
f[0] = 1;
for (int i = 0; i < s.length(); ++i) {
for (int j = t.length() - 1; j >= 0; --j) {
f[j + 1] += s.charAt(i) == t.charAt(j) ? f[j] : 0;
}
}

return f[t.length()];
}
}