Given a string S and a string T, count the number of distinct subsequences of T in S.
最开始，一感觉，这就是一个DFS。所以也就按dfs写了。但是超时。
想到了dp，但是觉得无法解决。因为当时想到的是1维动态规划，感觉这个问题，无法用子问题得到答案。
看到网上的解法，最后还是用的dp，不过是二维dp。
map[i][j]表示的是S中的前i个字符，有多少种方式可以表示T中的前j个字符。
if S[i] == T[j], map[i][j] = map[i-1][j] + map[i-1][j-1];
if S[i] != T[j], map[i][j] = map[i-1][j];
初始条件为：map[i][0] = 1; map[0][j] = 0; (j!=0);
1 public static int numDistinct(String S, String T) { 2 if (S.length() < T.length()) return 0; 3 int[][] map = new int[S.length()+1][T.length()+1]; 4 for (int i=0; i<=S.length(); i++) { 5 map[i][0] = 1; 6 } 7 8 for (int i=1; i<=S.length(); i++) { 9 for (int j=1; j<=T.length(); j++) { 10 if (S.charAt(i-1) == T.charAt(j-1)) 11 map[i][j] = map[i-1][j] + map[i-1][j-1]; 12 else 13 map[i][j] = map[i-1][j]; 14 } 15 } 16 17 return map[S.length()][T.length()]; 18 }
LeetCode: Distinct Subsequences,布布扣,bubuko.com
LeetCode: Distinct Subsequences
原文：http://www.cnblogs.com/longhorn/p/3593109.html