原题链接: http://oj.leetcode.com/problems/distinct-subsequences/
这道题应该很容易感觉到是动态规划的题目。还是老套路，先考虑我们要维护什么量。这里我们维护res[i][j]，对应的值是S的前i个字符和T的前j个字符有多少个可行的序列（注意这道题是序列，不是子串，也就是只要字符按照顺序出现即可，不需要连续出现）。下面来看看递推式，假设我们现在拥有之前的历史信息，我们怎么在常量操作时间内得到res[i][j]。假设S的第i个字符和T的第j个字符不相同，那么就意味着res[i][j]的值跟res[i-1][j]是一样的，前面该是多少还是多少，而第i个字符的加入也不会多出来任何可行结果。如果S的第i个字符和T的第j个字符相同，那么所有res[i-1][j-1]中满足的结果都会成为新的满足的序列，当然res[i-1][j]的也仍是可行结果，所以res[i][j]=[i-1][j-1]+res[i-1][j]。所以综合上面两种情况，递推式应该是res[i][j]=(S[i]==T[j]?res[i-1][j-1]:0)+res[i][j]。算法进行两层循环，时间复杂度是O(m*n)，而空间上只需要维护当前i对应的数据就可以，也就是O(m)。代码如下：
public int numDistinct(String S, String T) {
if(T.length()==0)
{
return 1;
}
if(S.length()==0)
return 0;
int[] res = new int[T.length()+1];
res[0] = 1;
for(int i=0;i<S.length();i++)
{
for(int j=T.length()-1;j>=0;j--)
{
res[j+1] = (S.charAt(i)==T.charAt(j)?res[j]:0)+res[j+1];
}
}
return res[T.length()];
}
返回栏目页：http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/
可以看到代码跟上面推导的递推式下标有点不同，因为下标从0开始，这种细节在实现的时候比较能想清楚，这里res[j+1]相当于T的前j个字符对应的串，少看一个。而res[0]表示一个字符都没有时的结果，最后结果返回res[T.length()]，对应于整个字符串的可行序列的数量。
作者：csdn博客 Caroline-Wendy
以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索oj
， leetcode
， 字符
， 结果
， res
， 序列
， length
下标
subsequences、leetcode、leetcode中文版、leetcode oj、leetcode题解，以便于您获取更多的相关知识。