Dynamic Programing Solution - Distinct Subsequences

Dynamic Programing - when don't know what to do… either recursive or DP… similar rule applies.

public class Solution {
    // public int numDistinct(String S, String T) {
    //     if(S == null || T == null) return -1;
    //     int[][] m = new int[T.length() + 1][S.length() + 1];
    //     for(int j = 0; j <= S.length(); j++) m[0][j] = 1;
    //     for(int i = 1; i <= T.length(); i++)
    //         for(int j = i; j <= S.length(); j++)
    //             m[i][j] = T.charAt(i-1) != S.charAt(j-1) ? m[i][j-1] : m[i-1][j-1] + m[i][j-1];
    //     return m[T.length()][S.length()];    
    // }
 
    public int numDistinct(String S, String T) {
        int[] occurence = new int[T.length() + 1];
        occurence[0] = 1;
        for(int i = 0; i < S.length(); i++){
            for(int j = T.length() - 1; j >= 0 ; j--)
                if(S.charAt(i) == T.charAt(j)){
                    if(occurence[j] > 0)
                        occurence[j + 1] += occurence[j];
                }
        }
        return occurence[T.length()];
    }
}

"子串的长度为 i，我们要求的就是长度为 i 的字串在长度为 j 的母串中出现的次数，设为 t[i][j]，若母串的最后一个字符与子串的最后一个字符不同，则长度为 i 的子串在长度为 j 的母串中出现的次数就是母串的前 j - 1 个字符中子串出现的次数，即 t[i][j] = t[i][j - 1]，若母串的最后一个字符与子串的最后一个字符相同，那么除了前 j - 1 个字符出现字串的次数外，还要加上子串的前 i - 1 个字符在母串的前 j - 1 个字符中出现的次数，即 t[i][j] = t[i][j - 1] + t[i - 1][j - 1]。  "   http://fisherlei.blogspot.com/2012/12/leetcode-distinct-subsequences_19.html