[leetcode] Distinct Subsequences

思路多了一点
再次做一次 还是先想想recursion开始吧帅哥！ 加上recursion 到bottom up 还要想想corner case 的initialization 还有bottom up方向
最后还别忘了滚动数组 重做：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

public class Solution { public int numDistinct(String s, String t) { if (s == null || t == null || s.length() < t.length()){ return 0; } if (t.length() == 0){ return s.length(); } int sL = s.length(); int tL = t.length(); int table[][] = new int[tL][sL]; table[tL-1][sL-1] = s.charAt(sL-1) == t.charAt(tL-1)?1:0; for (int i = s.length()-2; i >= 0; i--){ table[tL-1][i] = s.charAt(i) == t.charAt(tL-1)?table[tL-1][i+1]+1:table[tL-1][i+1]; } for (int i = tL - 2; i >= 0; i--){ table[i][sL-1] = 0; for (int j = sL - 2; j >= 0; j--){ table[i][j] = s.charAt(j) == t.charAt(i)? table[i+1][j+1]+table[i][j+1]:table[i][j+1]; } } return table[0][0]; } }