Distinct Subsequences

Well, this question is a typically DP one. At first sight, it reminds me of the "longest common subsequence " problem, where a matrix is applied, and one axis is String S, the other is String T. However, I didn't realize that similar method should also be used here. And as a result, one NOT good solution is come up, just like finding all possible ways to get distinct subsequences, while this is not necessary for this question. After checking out code ganker's code and explanation, I am so disappointed at myself. I really need to study DP again.
Anyway, thanks to him for his good post: http://blog.csdn.net/linhuanmars/article/details/23589057

Solution by code ganker:

 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()];  
 }  

Solution: my version(result is correct, but time complexity is more than O(m*n)), which gets TLE. Just for memory:

 public class Solution {  
   public int numDistinct(String S, String T) {  
     if(S == null || T== null || S.length()<T.length()) return 0;  
     if(S.length() == T.length()){  
       if(S.equals(T)) return 1;  
       else return 0;  
     }    
     int res = 0;  
     ArrayList<ArrayList<Integer>> dict = new ArrayList<ArrayList<Integer>>();  
     buildDict(S,T,dict);  
     int[] endIdx = new int[T.length()];  
     for(int i = 0; i < T.length(); i++){  
       ArrayList<Integer> tmpList = dict.get(i);  
       if(tmpList.isEmpty()) return 0;  
       endIdx[i] = tmpList.size()-1;  
     }  
     res = countNumDistinctSubseq(endIdx,dict,T.length() - 1,S.length());  
     // Use stack, DP  
     // boolean [][] dict = new boolean[T.length()][S.length()];  
     // buildDict(S,T,dict);  
     // int i = T.length() - 1, j = S.length() - 1;  
 //    while(j>=0){  
 //      if(dict[i][j]){  
         // res += countNumSubseq(i,j,dict);  
 //      }  
 //      j--;  
 //    }  
 //      
     return res;  
   }  
   public int countNumDistinctSubseq(String S, int[] endIdx, ArrayList<ArrayList<Integer>> dict, int level){  
     int res = 0;  
     ArrayList<Integer> crntLevel = dict.get(level);  
     // for(Integer crntIdx:crntLevel){  
       res += countNumDistinctSubseq(endIdx,dict,level - 1,S.length());  
     // }  
     return res;  
   }  
   public int countNumDistinctSubseq(int[] endIdx, ArrayList<ArrayList<Integer>> dict, int level, int idxFromPreLevel){  
     int numCrntLevel = 0;  
     // if(level < 0) level=0;  
     int endIdxLevel = endIdx[level];  
     ArrayList<Integer> crntLevel = dict.get(level);       
     if(level == 0){  
       for(int i = endIdxLevel; i >= 0; i--){  
         if(crntLevel.get(i) < idxFromPreLevel){  
           //endIdx[level] = i;  
           numCrntLevel = ++i; break;  
         }  
       }      
       return numCrntLevel;  
     }  
     int res = 0;  
     for(int i = endIdxLevel; i >= 0; i--){  
       if(crntLevel.get(i) < idxFromPreLevel){  
         //endIdx[level] = i;//idxFromPreLevel = crntLevel.get(i);numCrntLevel = ++i; break;  
         res += countNumDistinctSubseq(endIdx,dict,level - 1,crntLevel.get(i));  
       }  
     }  
     // res *= numCrntLevel * countNumDistinctSubseq(endIdx,dict,level - 1,idxFromPreLevel);  
     return res;  
   }  
   public void buildDict(String S, String T, ArrayList<ArrayList<Integer>> dict){  
     for(int i = 0 ; i < T.length() ; i++){  
       ArrayList<Integer> list = new ArrayList<Integer>();  
       for(int j = i; j < S.length();j++){  
         if(T.charAt(i) == S.charAt(j)){  
           list.add(j);  
         }  
       }  
       dict.add(list);  
     }  
   }    
   public void buildDict(String S, String T, boolean[][] dict){  
     for(int i = 0 ; i < T.length() ; i++){  
       for(int j = i; j < S.length();j++){  
         if(T.charAt(i) == S.charAt(j)){  
           dict[i][j] = true;  
         }  
       }  
     }  
   }   
   public int countNumSubseq(int level, int endIdx, boolean[][] dict){  
     int res = 0;  
     if(level==0 ){  
       for(int i = endIdx;i>=0; i--){  
         if(dict[level][i]) res++;  
       }  
     }  
     else{  
       for(int i = endIdx;i>=level;i--){  
         if(dict[level][i]){  
           res += countNumSubseq(level-1,i-1,dict);  
         }  
       }  
     }  
     return res;  
   }  
 }