LeetCode Distinct Subsequences

We try two possible solutions: DFS and DP

private static int disNum = 0;
public static int numDistinct(String S, String T) {
int[] flags =new int[S.length()];
int num=0;
dfs(num, flags, 0, 0, S, T);
return disNum;
}

private static void dfs(int num, int[] flags, int indexS, int indexT, String S,
String T) {
if (num==T.length()) {
disNum++;
} else {
for (int i=indexS; i<S.length(); i++) {
if (S.charAt(i)==T.charAt(indexT) && flags[i]==0) {
flags[i]=0;
num++;
dfs(num, flags, i+1, indexT+1, S, T);
flags[i]=0;
num--;
}
}
}
}

DP with 2D
public static int numDistictDP(String S, String T) {
int[][] dp = new int[T.length()+1][S.length()+1];
dp[0][0]=1;
for (int i=1; i<=S.length(); i++) {
dp[0][i]=1;
}
for (int i=1; i<=T.length(); i++) {
dp[i][0]=0;
}
for (int i=1; i<=T.length(); i++) {
for (int j=1; j<=S.length(); j++) {
if (T.charAt(i-1)==S.charAt(j-1)) {
dp[i][j] = dp[i-1][j-1] + dp[i][j-1];
} else {
dp[i][j] = dp[i][j-1];
}
}
}
return dp[T.length()][S.length()];
}

DP with optimized space
public int numDistinctDPOptimized(String S, String T) {
       // IMPORTANT: Please reset any member data you declared, as
       // the same Solution instance will be reused for each test case.
   if(S==null || T==null) return -1;
   int[] dp = new int[T.length()+1];
   dp[0]=1;
   for(int i=0; i<S.length();i++)
       for(int j=T.length(); j>0; j--)
           dp[j] += T.charAt(j-1)!=S.charAt(i)?0:dp[j-1];
 
   return dp[T.length()];
   }